Treffer: Homotopic Fréchet Distance Between Curves or, Walking Your Dog in the Woods in Polynomial Time
Title:
Homotopic Fréchet Distance Between Curves or, Walking Your Dog in the Woods in Polynomial Time
Authors:
Contributors:
University of Illinois at Urbana-Champaign [Urbana] (UIUC), University of Illinois System, École normale supérieure - Paris (ENS-PSL), Université Paris Sciences et Lettres (PSL), Department. of Computer Science [Illinois], Effective Geometric Algorithms for Surfaces and Visibility (VEGAS), INRIA Lorraine, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université Henri Poincaré - Nancy 1 (UHP)-Université Nancy 2-Institut National Polytechnique de Lorraine (INPL)-Centre National de la Recherche Scientifique (CNRS)-Université Henri Poincaré - Nancy 1 (UHP)-Université Nancy 2-Institut National Polytechnique de Lorraine (INPL)-Centre National de la Recherche Scientifique (CNRS), GIPSA - Architecture, Géométrie, Perception, Images, Gestes (GIPSA-AGPIG), Département Images et Signal (GIPSA-DIS), Grenoble Images Parole Signal Automatique (GIPSA-lab), Université Pierre Mendès France - Grenoble 2 (UPMF)-Université Stendhal - Grenoble 3-Université Joseph Fourier - Grenoble 1 (UJF)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP)-Centre National de la Recherche Scientifique (CNRS)-Université Pierre Mendès France - Grenoble 2 (UPMF)-Université Stendhal - Grenoble 3-Université Joseph Fourier - Grenoble 1 (UJF)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP)-Centre National de la Recherche Scientifique (CNRS)-Grenoble Images Parole Signal Automatique (GIPSA-lab), Université Pierre Mendès France - Grenoble 2 (UPMF)-Université Stendhal - Grenoble 3-Université Joseph Fourier - Grenoble 1 (UJF)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP)-Centre National de la Recherche Scientifique (CNRS)-Université Pierre Mendès France - Grenoble 2 (UPMF)-Université Stendhal - Grenoble 3-Université Joseph Fourier - Grenoble 1 (UJF)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP)-Centre National de la Recherche Scientifique (CNRS), Center for the Mathematics of Information (CMI), California Institute of Technology (CALTECH)
Source:
Computational Geometry. 43(3):295-311
Publisher Information:
CCSD; Elsevier, 2010.
Publication Year:
2010
Collection:
collection:ENS-PARIS
collection:UGA
collection:CNRS
collection:INRIA
collection:UNIV-GRENOBLE1
collection:UNIV-PMF_GRENOBLE
collection:UNIV-GRENOBLE3
collection:INPL
collection:INPG
collection:GIPSA
collection:GIPSA-DIS
collection:GIPSA-AGPIG
collection:INRIA-LORRAINE
collection:LORIA2
collection:INRIA-NANCY-GRAND-EST
collection:TESTALAIN1
collection:UGA-TEST-BIS
collection:UGA-TEST-QUATER
collection:UNIV-LORRAINE
collection:INRIA2
collection:LORIA
collection:PSL
collection:ENS-PSL
collection:INRIA-ETATSUNIS
collection:TEST-UGA
collection:AM2I-UL
collection:UGA
collection:CNRS
collection:INRIA
collection:UNIV-GRENOBLE1
collection:UNIV-PMF_GRENOBLE
collection:UNIV-GRENOBLE3
collection:INPL
collection:INPG
collection:GIPSA
collection:GIPSA-DIS
collection:GIPSA-AGPIG
collection:INRIA-LORRAINE
collection:LORIA2
collection:INRIA-NANCY-GRAND-EST
collection:TESTALAIN1
collection:UGA-TEST-BIS
collection:UGA-TEST-QUATER
collection:UNIV-LORRAINE
collection:INRIA2
collection:LORIA
collection:PSL
collection:ENS-PSL
collection:INRIA-ETATSUNIS
collection:TEST-UGA
collection:AM2I-UL
Subject Terms:
Original Identifier:
HAL:
Document Type:
Zeitschrift
article<br />Journal articles
Language:
English
ISSN:
0925-7721
Relation:
info:eu-repo/semantics/altIdentifier/doi/10.1016/j.comgeo.2009.02.008
DOI:
10.1016/j.comgeo.2009.02.008
Access URL:
Rights:
info:eu-repo/semantics/OpenAccess
Accession Number:
edshal.inria.00438463v1
Database:
HAL
Weitere Informationen
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.