The fréchet distance revisited and extended

Sariel Har-Peled, Benjamin Raichel

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Given two simplicial complexes in IRd, and start and end vertices in each complex, we show how to compute curves (in each complex) between these vertices, such that the Fré chetdistance between these curves is minimized. As a polygonal curve is a complex, this generalizes the regular notion of weak Fré chet distance between curves. We also generalize the algorithm to handle an input of k simplicial complexes. Using this new algorithm we can solve a slew of new problems, from computing a mean curve for a given collection of curves, to various motion planning problems. Additionally, we show that for the mean curve problem, when the k input curves are c-packed, one can (1 + ")-approximate the mean curve in near linear time, for fixed k and ". Additionally, we present an algorithm for computing the strong Fré chet distance between two curves, which is simpler than previous algorithms, and avoids using parametric search.

Original languageEnglish (US)
Title of host publicationProceedings of the 27th Annual Symposium on Computational Geometry, SCG'11
Pages448-457
Number of pages10
DOIs
StatePublished - 2011
Event27th Annual ACM Symposium on Computational Geometry, SCG'11 - Paris, France
Duration: Jun 13 2011Jun 15 2011

Publication series

NameProceedings of the Annual Symposium on Computational Geometry

Other

Other27th Annual ACM Symposium on Computational Geometry, SCG'11
CountryFrance
CityParis
Period6/13/116/15/11

Keywords

  • Approximation algorithms
  • Fréchet distance
  • Realistic input Models

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Geometry and Topology
  • Computational Mathematics

Fingerprint Dive into the research topics of 'The fréchet distance revisited and extended'. Together they form a unique fingerprint.

Cite this