Shortcuts for the circle
(2019) In Computational Geometry: Theory and Applications 79. p.37-54- 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[Formula presented]) for any k.
Please use this url to cite or link to this publication:
https://lup.lub.lu.se/record/d533f46b-e837-47b6-8933-2eca244db820
- author
- Bae, Sang Won ; de Berg, Mark ; Cheong, Otfried ; Gudmundsson, Joachim LU and Levcopoulos, Christos LU
- organization
- publishing date
- 2019-01-24
- type
- Contribution to journal
- publication status
- published
- subject
- keywords
- Geometric network, Graph augmentation, Graph diameter
- in
- Computational Geometry: Theory and Applications
- volume
- 79
- pages
- 37 - 54
- publisher
- Elsevier
- external identifiers
-
- scopus:85060736146
- ISSN
- 0925-7721
- DOI
- 10.1016/j.comgeo.2019.01.006
- language
- English
- LU publication?
- yes
- id
- d533f46b-e837-47b6-8933-2eca244db820
- date added to LUP
- 2019-02-07 12:48:48
- date last changed
- 2022-04-25 21:15:52
@article{d533f46b-e837-47b6-8933-2eca244db820, abstract = {{<p>Let C be the unit circle in R<sup>2</sup>. 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<sup>[Formula presented]</sup>) for any k.</p>}}, author = {{Bae, Sang Won and de Berg, Mark and Cheong, Otfried and Gudmundsson, Joachim and Levcopoulos, Christos}}, issn = {{0925-7721}}, keywords = {{Geometric network; Graph augmentation; Graph diameter}}, language = {{eng}}, month = {{01}}, pages = {{37--54}}, publisher = {{Elsevier}}, series = {{Computational Geometry: Theory and Applications}}, title = {{Shortcuts for the circle}}, url = {{http://dx.doi.org/10.1016/j.comgeo.2019.01.006}}, doi = {{10.1016/j.comgeo.2019.01.006}}, volume = {{79}}, year = {{2019}}, }