Abstract
Let C be the unit circle in R 2 . 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+Θ([formula presented]) for any k.
| Original language | English |
|---|---|
| Pages (from-to) | 37-54 |
| Number of pages | 18 |
| Journal | Computational Geometry |
| Volume | 79 |
| DOIs | |
| Publication status | Published - 1 Feb 2019 |
Fingerprint
Keywords
- Geometric network
- Graph augmentation
- Graph diameter
Cite this
}
Shortcuts for the circle. / Bae, Sang Won; de Berg, Mark; Cheong, Otfried (Corresponding author); Gudmundsson, Joachim; Levcopoulos, Christos.
In: Computational Geometry, Vol. 79, 01.02.2019, p. 37-54.Research output: Contribution to journal › Article › Academic › peer-review
TY - JOUR
T1 - Shortcuts for the circle
AU - Bae, Sang Won
AU - de Berg, Mark
AU - Cheong, Otfried
AU - Gudmundsson, Joachim
AU - Levcopoulos, Christos
PY - 2019/2/1
Y1 - 2019/2/1
N2 - Let C be the unit circle in R 2 . 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+Θ([formula presented]) for any k.
AB - Let C be the unit circle in R 2 . 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+Θ([formula presented]) for any k.
KW - Geometric network
KW - Graph augmentation
KW - Graph diameter
UR - http://www.scopus.com/inward/record.url?scp=85060736146&partnerID=8YFLogxK
U2 - 10.1016/j.comgeo.2019.01.006
DO - 10.1016/j.comgeo.2019.01.006
M3 - Article
AN - SCOPUS:85060736146
VL - 79
SP - 37
EP - 54
JO - Computational Geometry
JF - Computational Geometry
SN - 0925-7721
ER -