Shortcuts for the circle

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

Onderzoeksoutput: Bijdrage aan tijdschriftTijdschriftartikelAcademicpeer review

2 Citaten (Scopus)
149 Downloads (Pure)

Samenvatting

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.

Originele taal-2Engels
Pagina's (van-tot)37-54
Aantal pagina's18
TijdschriftComputational Geometry
Volume79
DOI's
StatusGepubliceerd - 1 feb. 2019

Vingerafdruk

Duik in de onderzoeksthema's van 'Shortcuts for the circle'. Samen vormen ze een unieke vingerafdruk.

Citeer dit