Home Bookmarks Papers Blog

New Similarity Measures between Polylines with Applications to Morphing and Polygon Sweeping

Alon Efrat, Leonidas J. Guibas, Sariel Har-Peled, Joseph S. B. Mitchell, and T.~M. Murali


We introduce two new related metrics, the geodesic width and the link width, for measuring the ``distance'' between two non-intersecting polylines in the plane. If the two polylines have n vertices in total, we present algorithms to compute the geodesic width of the two polylines in O(n2 log n) time using O(n2) space and the link width in O(n3 log n) time using O(n2) working space. Our computation of these metrics relies on two closely-related combinatorial strutures: the shortest-path diagram and the link diagram of a simple polygon. The shortest-path(resp., link) diagram encodes the Euclidean(resp., link) shortest path distance between all pairs of points on the boundary of the polygon. We use these algorithms to solve two problems:
Postscript : PDF
@string{DCG    = "Discrete Comput. Geom."}

@Article{ehgmm-nsmpa-02,
  author       = {A. Efrat and S. {Har-Peled} and L. J. Guibas and
                  J. S.B. Mitchell and T.M. Murali},
  title        = {New Similarity Measures between Polylines with
                  Applications to Morphing and Polygon Sweeping},
  journal      = DCG,
  year         = 2002,
  volume       = 28,
  pages        = {535--569}
}

This paper is based on the following conference papers:
Last modified: Wed Jul 20 15:58:19 CDT 2011 Last updated: Sun Aug 26 11:05:47 CDT 2001