Chambers, Erin Wolf and Colin de Verdière, Éric and Erickson, Jeff and Lazard, Sylvain and Lazarus, Francis and Thite, Shripad (2010) Homotopic Fréchet distance between curves or, walking your dog in the woods in polynomial time. Computational Geometry, 43 (3). pp. 295-311. ISSN 0925-7721 http://resolver.caltech.edu/CaltechAUTHORS:20100104-122144068
- Published Version
Restricted to Repository administrators only
See Usage Policy.
Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechAUTHORS:20100104-122144068
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.
|Additional Information:||© 2009 Elsevier. Received 1 September 2008; revised 8 January 2009; accepted 19 February 2009. Communicated by M. Teillaud. Available online 4 May 2009. 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.|
|Subject Keywords:||Homotopy; Similarity of curves; Metric space; Homotopic Fréchet distance; Geodesic leash map; Punctured plane|
|Usage Policy:||No commercial reproduction, distribution, display or performance rights in this work are provided.|
|Deposited By:||Jason Perez|
|Deposited On:||04 Jan 2010 21:59|
|Last Modified:||26 Dec 2012 11:40|
Repository Staff Only: item control page