Near-linear time approximation algorithms for curve simplification

Pankaj K. Agarwal, Sariel Har-Peled, Nabil H. Mustafa, Yusu Wang

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

Abstract

We consider the problem of approximating a polygonal curve P under a given error criterion by another polygonal curve P' whose vertices are a subset of the vertices of P. The goal is to minimize the number of vertices of P' while ensuring that the error between P' and P is below a certain threshold. We consider two fundamentally different error measures — Hausdorff and Frechet error measures. For both error criteria, we present near-linear time approximation algorithms that, given a parameter e ε 0, compute a simplified polygonal curve P' whose error is less than e and size at most the size of an optimal simplified polygonal curve with error ε/2. We consider monotone curves in the case of Hausdorff error measure and arbitrary curves for the Fréchet error measure. We present experimental results demonstrating that our algorithms are simple and fast, and produce close to optimal simplifications in practice.

Original languageEnglish (US)
Title of host publicationAlgorithms - ESA 2002 - 10th Annual European Symposium, Proceedings
EditorsRolf Möhring, Rajeev Raman
PublisherSpringer
Pages29-41
Number of pages13
ISBN (Electronic)3540441808, 9783540441809
DOIs
StatePublished - 2002
Event10th Annual European Symposium on Algorithms, ESA 2002 - Rome, Italy
Duration: Sep 17 2002Sep 21 2002

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume2461
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other10th Annual European Symposium on Algorithms, ESA 2002
Country/TerritoryItaly
CityRome
Period9/17/029/21/02

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint

Dive into the research topics of 'Near-linear time approximation algorithms for curve simplification'. Together they form a unique fingerprint.

Cite this