Shortcuts for the circle
(2017) 28th International Symposium on Algorithms and Computation, ISAAC 2017 In 28th International Symposium on Algorithms and Computation, ISAAC 2017 92. p.113 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 2 3 ) for any k.
Please use this url to cite or link to this publication:
http://lup.lub.lu.se/record/c0a5779e788d4ba982e3d0babcb0f36a
 author
 Bae, Sang Won; De Berg, Mark; Cheong, Otfried; Gudmundsson, Joachim ^{LU} and Levcopoulos, Christos ^{LU}
 organization
 publishing date
 20171201
 type
 Chapter in Book/Report/Conference proceeding
 publication status
 published
 subject
 keywords
 Circle, Computational geometry, Diameter, Graph augmentation problem, Shortcut
 in
 28th International Symposium on Algorithms and Computation, ISAAC 2017
 volume
 92
 pages
 1  13
 publisher
 Schloss Dagstuhl LeibnizZentrum fur Informatik GmbH, Dagstuhl Publishing
 conference name
 28th International Symposium on Algorithms and Computation, ISAAC 2017
 external identifiers

 scopus:85038563025
 ISBN
 9783959770545
 DOI
 10.4230/LIPIcs.ISAAC.2017.9
 language
 English
 LU publication?
 yes
 id
 c0a5779e788d4ba982e3d0babcb0f36a
 date added to LUP
 20180104 08:03:55
 date last changed
 20180529 10:35:53
@inproceedings{c0a5779e788d4ba982e3d0babcb0f36a, abstract = {<p>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 2 3 ) for any k.</p>}, author = {Bae, Sang Won and De Berg, Mark and Cheong, Otfried and Gudmundsson, Joachim and Levcopoulos, Christos}, booktitle = {28th International Symposium on Algorithms and Computation, ISAAC 2017}, isbn = {9783959770545}, keyword = {Circle,Computational geometry,Diameter,Graph augmentation problem,Shortcut}, language = {eng}, month = {12}, pages = {113}, publisher = {Schloss Dagstuhl LeibnizZentrum fur Informatik GmbH, Dagstuhl Publishing}, title = {Shortcuts for the circle}, url = {http://dx.doi.org/10.4230/LIPIcs.ISAAC.2017.9}, volume = {92}, year = {2017}, }