文章基本信息

标题：Shortcuts for the Circle
本地全文：下载
作者：Sang Won Bae ; Mark de Berg ; Otfried Cheong 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2017
卷号：92
页码：9:1-9:13
DOI：10.4230/LIPIcs.ISAAC.2017.9
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：Computational geometry; graph augmentation problem; circle; shortcut; diameter