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.
| Original language | English |
|---|---|
| Title of host publication | ISAAC 2017 : 28th International Symposium on Algorithms and Computation, 9-12 December 2017, Phuket, Thailand |
| Editors | Takeshi Tokuyama, Yoshio Okamoto |
| Place of Publication | Dagstuhl |
| Publisher | Schloss Dagstuhl - Leibniz-Zentrum für Informatik |
| Pages | 9:1-9:13 |
| ISBN (Electronic) | 9783959770545 |
| ISBN (Print) | 978-3-95977-054-5 |
| DOIs | |
| Publication status | Published - 2017 |
| Event | 28th International Symposium on Algorithms and Computation (ISAAC 2017) - Phuket, Thailand Duration: 9 Dec 2017 → 12 Dec 2017 Conference number: 28 http://aiat.in.th/isaac2017/ |
Publication series
| Name | Leibniz International Proceedings in Informatics, LIPIcs |
|---|---|
| Volume | 92 |
| ISSN (Print) | 1868-8969 |
Conference
| Conference | 28th International Symposium on Algorithms and Computation (ISAAC 2017) |
|---|---|
| Abbreviated title | ISAAC 2017 |
| Country/Territory | Thailand |
| City | Phuket |
| Period | 9/12/17 → 12/12/17 |
| Internet address |
Keywords
- Circle
- Computational geometry
- Diameter
- Graph augmentation problem
- Shortcut
Fingerprint
Dive into the research topics of 'Shortcuts for the circle'. Together they form a unique fingerprint.Cite this
- APA
- Author
- BIBTEX
- Harvard
- Standard
- RIS
- Vancouver