Approximating the Fréchet distance for realistic curves in near linear time

Anne Driemel, Sariel Har-Peled, Carola Wenk

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

Abstract

We present a simple and practical (1+ε)-approximation algorithm for the Fréchet distance between polygonal curves. To analyze this algorithm we introduce a new realistic family of curves, c-packed curves, that is closed under simplification. We believe the notion of c-packed curves to be of independent interest. We show that our algorithm has near linear running time for c-packed polygonal curves, and show similar results for other input models, such as low density.

Original languageEnglish (US)
Title of host publicationProceedings of the 26th Annual Symposium on Computational Geometry, SCG'10
Pages365-374
Number of pages10
DOIs
StatePublished - 2010
Event26th Annual Symposium on Computational Geometry, SoCG 2010 - Snowbird, UT, United States
Duration: Jun 13 2010Jun 16 2010

Publication series

NameProceedings of the Annual Symposium on Computational Geometry

Other

Other26th Annual Symposium on Computational Geometry, SoCG 2010
Country/TerritoryUnited States
CitySnowbird, UT
Period6/13/106/16/10

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 'Approximating the Fréchet distance for realistic curves in near linear time'. Together they form a unique fingerprint.

Cite this