A Caltech Library Service

Homotopic Fréchet distance between curves or, walking your dog in the woods in polynomial time

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.

Full text is not posted in this repository. Consult Related URLs below.

Use this Persistent URL to link to this item:


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.

Item Type:Article
Related URLs:
URLURL TypeDescription
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.
Funding AgencyGrant Number
NSF Graduate Research FellowshipUNSPECIFIED
Nederlandse Organisatie voor Wetenschappelijk Onderzoek (NWO)639.023.301
University of Illinois Urbana-ChampaignUNSPECIFIED
Centre National de la Recherche Scientifique (CNRS)UNSPECIFIED
Inventeurs du monde numérique (INRIA)UNSPECIFIED
Subject Keywords:Homotopy; Similarity of curves; Metric space; Homotopic Fréchet distance; Geodesic leash map; Punctured plane
Issue or Number:3
Record Number:CaltechAUTHORS:20100104-122144068
Persistent URL:
Official Citation:Monique Teillaud, Erin Wolf Chambers, Éric Colin de Verdière, Jeff Erickson, Sylvain Lazard, Francis Lazarus, Shripad Thite, Special Issue on 24th Annual Symposium on Computational Geometry (SoCG'08)Homotopic Fréchet distance between curves or, walking your dog in the woods in polynomial time, Computational Geometry, Volume 43, Issue 3, 2010, Pages 295-311, ISSN 0925-7721, (
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:17051
Deposited By: Jason Perez
Deposited On:04 Jan 2010 21:59
Last Modified:03 Oct 2019 01:21

Repository Staff Only: item control page