Shortcuts for the circle

S.W. Bae, M.T. de Berg, O. Cheong, J. Gudmundsson

Onderzoeksoutput: Boek/rapportRapportAcademic


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 6 k 6 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 23 ) for any k.
Originele taal-2Engels
Plaats van productieCornell
UitgeverijCornell University Library
Aantal pagina's21
StatusGepubliceerd - 8 dec 2016


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

Citeer dit