Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH scholarly article en Bae, Sang Won; de Berg, Mark; Cheong, Otfried; Gudmundsson, Joachim; Levcopoulos, Christos http://www.dagstuhl.de/lipics License
when quoting this document, please refer to the following
DOI:
URN: urn:nbn:de:0030-drops-82133
URL:

; ; ; ;

Shortcuts for the Circle

pdf-format:


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
Seminar: 28th International Symposium on Algorithms and Computation (ISAAC 2017)
Issue date: 2017
Date of publication: 2017


DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI