The Fréchet distance revisited and extended

Sariel Har-Peled, Benjamin Raichel

Research output: Contribution to journalArticlepeer-review

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 weak Fréchet distance 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)
Article number3
JournalACM Transactions on Algorithms
Volume10
Issue number1
DOIs
StatePublished - Jan 2014

Keywords

  • Algorithms
  • Approximation algorithms
  • F.2.2 [analysis of algorithms and problem complexity]: nonnumerical algorithms and problems - geometrical problems and computations
  • Fréchet distance
  • Realistic input models
  • Theory

ASJC Scopus subject areas

  • Mathematics (miscellaneous)

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

Cite this