# Lund University Publications

## LUND UNIVERSITY LIBRARIES

### 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.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.

author
organization
publishing date
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- Leibniz-Zentrum 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
c0a5779e-788d-4ba9-82e3-d0babcb0f36a
2018-01-04 08:03:55
date last changed
2018-05-29 10:35:53
```@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},
keyword      = {Circle,Computational geometry,Diameter,Graph augmentation problem,Shortcut},
language     = {eng},
month        = {12},
pages        = {1--13},
publisher    = {Schloss Dagstuhl- Leibniz-Zentrum 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},
}

```