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.

Additional Metadata
Keywords Dilation, Edge removal, Polygonal cycle
Persistent URL
Journal International Journal of Computational Geometry and Applications
Ahn, H.-K. (Hee-Kap), Farshi, M. (Mohammad), Knauer, C. (Christian), Smid, M, & Wang, Y. (Yajun). (2010). Dilation-optimal edge deletion in polygonal cycles. International Journal of Computational Geometry and Applications, 20(1), 69–87. doi:10.1142/S0218195910003207