Shortcuts for the circle

Sang Won Bae, Mark de Berg, Otfried Cheong (Corresponding author), Joachim Gudmundsson, Christos Levcopoulos

Research output: Contribution to journalArticleAcademicpeer-review

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+Θ([formula presented]) for any k.

Original languageEnglish
Pages (from-to)37-54
Number of pages18
JournalComputational Geometry
Volume79
DOIs
Publication statusPublished - 1 Feb 2019

Fingerprint

Circle
Plane Graph
Augmentation
Graph in graph theory
Unit circle
Arc of a curve
Strictly

Keywords

  • Geometric network
  • Graph augmentation
  • Graph diameter

Cite this

Bae, S. W., de Berg, M., Cheong, O., Gudmundsson, J., & Levcopoulos, C. (2019). Shortcuts for the circle. Computational Geometry, 79, 37-54. https://doi.org/10.1016/j.comgeo.2019.01.006
Bae, Sang Won ; de Berg, Mark ; Cheong, Otfried ; Gudmundsson, Joachim ; Levcopoulos, Christos. / Shortcuts for the circle. In: Computational Geometry. 2019 ; Vol. 79. pp. 37-54.
@article{9679b02bc804422b9031149454d0e0c2,
title = "Shortcuts for the circle",
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+Θ([formula presented]) for any k.",
keywords = "Geometric network, Graph augmentation, Graph diameter",
author = "Bae, {Sang Won} and {de Berg}, Mark and Otfried Cheong and Joachim Gudmundsson and Christos Levcopoulos",
year = "2019",
month = "2",
day = "1",
doi = "10.1016/j.comgeo.2019.01.006",
language = "English",
volume = "79",
pages = "37--54",
journal = "Computational Geometry",
issn = "0925-7721",
publisher = "Elsevier",

}

Bae, SW, de Berg, M, Cheong, O, Gudmundsson, J & Levcopoulos, C 2019, 'Shortcuts for the circle', Computational Geometry, vol. 79, pp. 37-54. https://doi.org/10.1016/j.comgeo.2019.01.006

Shortcuts for the circle. / Bae, Sang Won; de Berg, Mark; Cheong, Otfried (Corresponding author); Gudmundsson, Joachim; Levcopoulos, Christos.

In: Computational Geometry, Vol. 79, 01.02.2019, p. 37-54.

Research output: Contribution to journalArticleAcademicpeer-review

TY - JOUR

T1 - Shortcuts for the circle

AU - Bae, Sang Won

AU - de Berg, Mark

AU - Cheong, Otfried

AU - Gudmundsson, Joachim

AU - Levcopoulos, Christos

PY - 2019/2/1

Y1 - 2019/2/1

N2 - 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+Θ([formula presented]) for any k.

AB - 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+Θ([formula presented]) for any k.

KW - Geometric network

KW - Graph augmentation

KW - Graph diameter

UR - http://www.scopus.com/inward/record.url?scp=85060736146&partnerID=8YFLogxK

U2 - 10.1016/j.comgeo.2019.01.006

DO - 10.1016/j.comgeo.2019.01.006

M3 - Article

AN - SCOPUS:85060736146

VL - 79

SP - 37

EP - 54

JO - Computational Geometry

JF - Computational Geometry

SN - 0925-7721

ER -

Bae SW, de Berg M, Cheong O, Gudmundsson J, Levcopoulos C. Shortcuts for the circle. Computational Geometry. 2019 Feb 1;79:37-54. https://doi.org/10.1016/j.comgeo.2019.01.006