Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

Shortcuts for the circle

Bae, Sang Won ; De Berg, Mark ; Cheong, Otfried ; Gudmundsson, Joachim LU and Levcopoulos, Christos LU orcid (2017) 28th International Symposium on Algorithms and Computation, ISAAC 2017 92. p.1-13
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:
author
; ; ; and
organization
publishing date
type
Chapter in Book/Report/Conference proceeding
publication status
published
subject
keywords
Circle, Computational geometry, Diameter, Graph augmentation problem, Shortcut
host publication
28th International Symposium on Algorithms and Computation, ISAAC 2017
volume
92
pages
1 - 13
publisher
Schloss Dagstuhl - Leibniz-Zentrum für Informatik
conference name
28th International Symposium on Algorithms and Computation, ISAAC 2017
conference location
Phuket, Thailand
conference dates
2017-12-09 - 2017-12-22
external identifiers
  • scopus:85038563025
ISBN
9783959770545
DOI
10.4230/LIPIcs.ISAAC.2017.9
language
English
LU publication?
yes
id
c0a5779e-788d-4ba9-82e3-d0babcb0f36a
date added to LUP
2018-01-04 08:03:55
date last changed
2022-04-25 04:50:57
@inproceedings{c0a5779e-788d-4ba9-82e3-d0babcb0f36a,
  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}},
  keywords     = {{Circle; Computational geometry; Diameter; Graph augmentation problem; Shortcut}},
  language     = {{eng}},
  month        = {{12}},
  pages        = {{1--13}},
  publisher    = {{Schloss Dagstuhl - Leibniz-Zentrum für Informatik}},
  title        = {{Shortcuts for the circle}},
  url          = {{http://dx.doi.org/10.4230/LIPIcs.ISAAC.2017.9}},
  doi          = {{10.4230/LIPIcs.ISAAC.2017.9}},
  volume       = {{92}},
  year         = {{2017}},
}