Volume: 20, Issue: 1(2010)
pp. 69-87 DOI: 10.1142/S0218195910003207
|
|
Abstract |
Full Text (PDF, 300KB)
|
References
|
 |
| Title: |
DILATION-OPTIMAL EDGE DELETION IN POLYGONAL CYCLES
Part of this work was done during the Korean Workshop on Computational Geometry at Schloß Dagstuhl in 2006. Work by Ahn was supported by the Korea Research Foundation Grant funded by the Korean Government (MOEHRD, Basic Research Promotion Fund) (KRF-2007-331-D00372). Work by Farshi was supported by Ministry of Science, Research and Technology of I. R. Iran. Work by Smid was supported by NSERC.
|
| Author(s): |
HEE-KAP AHN
Department of Computer Science and Engineering, Pohang University of Science and Technology, Pohang, 790-784, KoreaMOHAMMAD FARSHI
School of Computer Science, Carleton University, Ottawa, Ontario, K1S 5B6, Canada
Department of Computer Science, Yazd University, P.O. Box. 89195-741, Yazd, IranCHRISTIAN KNAUER
Institut für Informatik, Freie Universität Berlin, Takustraße 9, D–14195 Berlin, GermanyMICHIEL SMID
School of Computer Science, Carleton University, Ottawa, Ontario, K1S 5B6, CanadaYAJUN WANG
Microsoft Research Asia, Beijing, China
|
| History: |
Received 12 December 2007
Revised 23 September 2008
|
| 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 log3 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 - ϵ)-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
|
|
|
