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 -