Shortcuts for the circle

Cited 0 time in webofscience Cited 0 time in scopus
  • Hit : 254
  • Download : 0
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 >= I 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. (C) 2019 Elsevier B.V. All rights reserved.
Publisher
ELSEVIER SCIENCE BV
Issue Date
2019-02
Language
English
Article Type
Article
Citation

COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS, v.79, pp.37 - 54

ISSN
0925-7721
DOI
10.1016/j.comgeo.2019.01.006
URI
http://hdl.handle.net/10203/261014
Appears in Collection
CS-Journal Papers(저널논문)
Files in This Item
There are no files associated with this item.

qr_code

  • mendeley

    citeulike


rss_1.0 rss_2.0 atom_1.0