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 -