TY - JOUR
T1 - Homotopic Fréchet distance between curves or, walking your dog in the woods in polynomial time
AU - Chambers, Erin Wolf
AU - Colin De Verdière, Éric
AU - Erickson, Jeff
AU - Lazard, Sylvain
AU - Lazarus, Francis
AU - Thite, Shripad
N1 - Funding Information:
This research was initiated during a visit to INRIA Lorraine in Nancy, made possible by a UIUC-CNRS-INRIA travel grant. Research by Erin Chambers and Jeff Erickson was also partially supported by NSF grant DMS-0528086; Erin Chambers was additionally supported by an NSF graduate research fellowship. Research by Shripad Thite was partially supported by the Netherlands Organisation for Scientific Research (NWO) under project number 639.023.301 and travel by INRIA Lorraine. We would like to thank the anonymous referees for their careful reading of the paper and their numerous suggestions for improvement. Finally, we thank Hazel Everett and Sylvain Petitjean for useful discussions, and Kira and Nori for great company and several walks in the woods.
PY - 2010/4
Y1 - 2010/4
N2 - The Fréchet distance between two curves in the plane is the minimum length of a leash that allows a dog and its owner to walk along their respective curves, from one end to the other, without backtracking. We propose a natural extension of Fréchet distance to more general metric spaces, which requires the leash itself to move continuously over time. For example, for curves in the punctured plane, the leash cannot pass through or jump over the obstacles ("trees"). We describe a polynomial-time algorithm to compute the homotopic Fréchet distance between two given polygonal curves in the plane minus a given set of polygonal obstacles.
AB - The Fréchet distance between two curves in the plane is the minimum length of a leash that allows a dog and its owner to walk along their respective curves, from one end to the other, without backtracking. We propose a natural extension of Fréchet distance to more general metric spaces, which requires the leash itself to move continuously over time. For example, for curves in the punctured plane, the leash cannot pass through or jump over the obstacles ("trees"). We describe a polynomial-time algorithm to compute the homotopic Fréchet distance between two given polygonal curves in the plane minus a given set of polygonal obstacles.
KW - Geodesic leash map
KW - Homotopic Fréchet distance
KW - Homotopy
KW - Metric space
KW - Punctured plane
KW - Similarity of curves
UR - http://www.scopus.com/inward/record.url?scp=84867971275&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84867971275&partnerID=8YFLogxK
U2 - 10.1016/j.comgeo.2009.02.008
DO - 10.1016/j.comgeo.2009.02.008
M3 - Article
AN - SCOPUS:84867971275
SN - 0925-7721
VL - 43
SP - 295
EP - 311
JO - Computational Geometry: Theory and Applications
JF - Computational Geometry: Theory and Applications
IS - 3
ER -