Shortcuts for the circle

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.

De Berg, MarkEindhoven University of Technology (författare)
Cheong, OtfriedKorea Advanced Institute of Science and Technology (KAIST) (författare)
Gudmundsson, JoachimUniversity of Sydney(Swepub:lu)csz-jmg (författare)
Levcopoulos, ChristosLund University,Lunds universitet,Institutionen för datavetenskap,Institutioner vid LTH,Lunds Tekniska Högskola,Department of Computer Science,Departments at LTH,Faculty of Engineering, LTH(Swepub:lu)cs-cle (författare)
Kyonggi UniversityEindhoven University of Technology (creator_code:org_t)

Ingår i:28th International Symposium on Algorithms and Computation, ISAAC 201792, s. 1-139783959770545

Av författaren/redakt...: Bae, Sang Won; De Berg, Mark; Cheong, Otfried; Gudmundsson, Joa ...; Levcopoulos, Chr ...

Om ämnet

Kungliga biblioteket hanterar dina personuppgifter i enlighet med EU:s dataskyddsförordning (2018), GDPR. Läs mer om hur det funkar här.
Så här hanterar KB dina uppgifter vid användning av denna tjänst.