Go to the corresponding LIPIcs Volume Portal |
Bae, Sang Won ;
de Berg, Mark ;
Cheong, Otfried ;
Gudmundsson, Joachim ;
Levcopoulos, Christos
Shortcuts for the Circle
pdf-format:
LIPIcs-ISAAC-2017-9.pdf (0.8 MB)
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 + Theta(1/k^(2/3)) for any k.BibTeX - Entry
@InProceedings{bae_et_al:LIPIcs:2017:8213,
author = {Sang Won Bae and Mark de Berg and Otfried Cheong and Joachim Gudmundsson and Christos Levcopoulos},
title = {{Shortcuts for the Circle}},
booktitle = {28th International Symposium on Algorithms and Computation (ISAAC 2017)},
pages = {9:1--9:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-054-5},
ISSN = {1868-8969},
year = {2017},
volume = {92},
editor = {Yoshio Okamoto and Takeshi Tokuyama},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/8213},
URN = {urn:nbn:de:0030-drops-82133},
doi = {10.4230/LIPIcs.ISAAC.2017.9},
annote = {Keywords: Computational geometry, graph augmentation problem, circle, shortcut, diameter}
}
Keywords:
Computational geometry, graph augmentation problem, circle, shortcut, diameter
Collection:
28th International Symposium on Algorithms and Computation (ISAAC 2017)
Issue Date:
2017
Date of publication:
07.12.2017