2026-07-22T21:45:00Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:8213 2024-03-06T10:41:46Z ddc:004 open_access

Shortcuts for the Circle Bae, Sang Won de Berg, Mark Cheong, Otfried Gudmundsson, Joachim Levcopoulos, Christos Computational geometry graph augmentation problem circle shortcut diameter 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 + Theta(1/k^(2/3)) for any k. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Sang Won Bae and Mark de Berg and Otfried Cheong and Joachim Gudmundsson and Christos Levcopoulos 2017 Is Part Of LIPIcs, Volume 92, 28th International Symposium on Algorithms and Computation (ISAAC 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ISAAC.2017.9 urn:nbn:de:0030-drops-82133 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2017.9 eng https://creativecommons.org/licenses/by/3.0/legalcode