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:
Compute a continuous transformation that ``morphs'' one polyline
into another polyline. Our morphing strategies ensure that each point
on a polyline moves as little as necessary during the morphing, that
every intermediate polyline is also simple, and that no portion of the
polylines to be morphed is stretched or compressed by more than a
user-defined parameter during the entire morphing. We present an
algorithm that computes the geodesic width of the two polylines and
utilizes it to construct a corresponding morphing strategy in
O(n2 log2 n) time using
O(n2) space. We also give an O(n log n) time
algorithm to compute a 2-approximation of the geodesic width and a
corresponding morphing scheme.
Locate a continuously-moving target using a group of guards
moving inside a simple polygon. The guards always determine a
simple polygonal chain within the polygon, with consecutive guards
along the chain being mutually visible. We compute a strategy
that sweeps such a chain of guards through the polygon in order
to locate a target. We compute in O(n3) time
and O(n2) working space the minimum number
r* of guards needed to sweep an n-vertex
polygon. We also give an approximation algorithm, using O(n
log n) time and O(n) space, to compute an integer
r such that \max(r - 16, 2)<= r*<= r
and P can be swept with a chain of r guards.
@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: