Shortcuts for the circle
Bae, Sang Won ; de Berg, Mark ; Cheong, Otfried ; Gudmundsson, Joachim LU and Levcopoulos, Christos LU
(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}},
}