DILATION-OPTIMAL EDGE DELETION IN POLYGONAL CYCLES
SCIE
SCOPUS
- Title
- DILATION-OPTIMAL EDGE DELETION IN POLYGONAL CYCLES
- Authors
- Ahn, HK; Farshi, M; Knauer, C; Smid, M; Wang, YJ
- Date Issued
- 2010-02
- Publisher
- WORLD SCIENTIFIC PUBL CO PTE LTD
- Abstract
- Consider a geometric network G in the plane. The dilation between any two vertices x and y in G is the ratio of the shortest path distance between x and y in G to the Euclidean distance between them. The maximum dilation over all pairs of vertices in G is called the dilation of G. In this paper, a randomized algorithm is presented which, when given a polygonal cycle C on n vertices in the plane, computes in O(n log(3) n) expected time, the edge of C whose removal results in a polygonal path of smallest possible dilation. It is also shown that the edge whose removal gives a polygonal path of largest possible dilation can be computed in O(n log n) time. If C is a convex polygon, the running time for the latter problem becomes O(n). Finally, it is shown that a(1 - epsilon)-approximation to the dilation of every path C\{e}, for all edges e of C, can be computed in O(n log n) total time.
- Keywords
- Dilation; polygonal cycle; edge removal; STRETCH FACTOR; ALGORITHM; TIME
- URI
- https://oasis.postech.ac.kr/handle/2014.oak/26487
- DOI
- 10.1142/S0218195910003207
- ISSN
- 0218-1959
- Article Type
- Article
- Citation
- INTERNATIONAL JOURNAL OF COMPUTATIONAL GEOMETRY & APPLICATIONS, vol. 20, no. 1, page. 69 - 87, 2010-02
- Files in This Item:
- There are no files associated with this item.
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.