Advanced

Shortcuts for the circle

Bae, Sang Won; De Berg, Mark; Cheong, Otfried; Gudmundsson, Joachim LU and Levcopoulos, Christos LU (2017) 28th International Symposium on Algorithms and Computation, ISAAC 2017 In 28th International Symposium on Algorithms and Computation, ISAAC 2017 92. p.1-13
Abstract

Let C be the unit circle in R2. We can view C as a plane graph whose vertices are all the points on C, and the distance between any two points on C is the length of the smaller arc between them. We consider a graph augmentation problem on C, where we want to place k ≥ 1 shortcuts on C such that the diameter of the resulting graph is minimized. We analyze for each k with 1 ≤ k ≤ 7 what the optimal set of shortcuts is. Interestingly, the minimum diameter one can obtain is not a strictly decreasing function of k. For example, with seven shortcuts one cannot obtain a smaller diameter than with six shortcuts. Finally, we prove that the optimal diameter is 2 + ⊖ (1/k 2 3 ) for any k.

Please use this url to cite or link to this publication:
author
organization
publishing date
type
Chapter in Book/Report/Conference proceeding
publication status
published
subject
keywords
Circle, Computational geometry, Diameter, Graph augmentation problem, Shortcut
in
28th International Symposium on Algorithms and Computation, ISAAC 2017
volume
92
pages
1 - 13
publisher
Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
conference name
28th International Symposium on Algorithms and Computation, ISAAC 2017
external identifiers
  • scopus:85038563025
ISBN
9783959770545
DOI
10.4230/LIPIcs.ISAAC.2017.9
language
English
LU publication?
yes
id
c0a5779e-788d-4ba9-82e3-d0babcb0f36a
date added to LUP
2018-01-04 08:03:55
date last changed
2018-01-04 08:03:55
@inproceedings{c0a5779e-788d-4ba9-82e3-d0babcb0f36a,
  abstract     = {<p>Let C be the unit circle in R2. We can view C as a plane graph whose vertices are all the points on C, and the distance between any two points on C is the length of the smaller arc between them. We consider a graph augmentation problem on C, where we want to place k ≥ 1 shortcuts on C such that the diameter of the resulting graph is minimized. We analyze for each k with 1 ≤ k ≤ 7 what the optimal set of shortcuts is. Interestingly, the minimum diameter one can obtain is not a strictly decreasing function of k. For example, with seven shortcuts one cannot obtain a smaller diameter than with six shortcuts. Finally, we prove that the optimal diameter is 2 + ⊖ (1/k 2 3 ) for any k.</p>},
  author       = {Bae, Sang Won and De Berg, Mark and Cheong, Otfried and Gudmundsson, Joachim and Levcopoulos, Christos},
  booktitle    = {28th International Symposium on Algorithms and Computation, ISAAC 2017},
  isbn         = {9783959770545},
  keyword      = {Circle,Computational geometry,Diameter,Graph augmentation problem,Shortcut},
  language     = {eng},
  month        = {12},
  pages        = {1--13},
  publisher    = {Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing},
  title        = {Shortcuts for the circle},
  url          = {http://dx.doi.org/10.4230/LIPIcs.ISAAC.2017.9},
  volume       = {92},
  year         = {2017},
}