Near-linear time approximation algorithms for curve simplification

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

Research output: Contribution to journalArticlepeer-review


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 different error measures: Hausdorff and Frechet. For both error criteria, we present near-linear time approximation algorithms that, given a parameter ε > 0, compute a simplified polygonal curve P' whose error is less than ε and size at most the size of an optimal simplified polygonal curve with error ε/2. We consider monotone curves in ℝ2 in the case of the Hausdorff error measure under the uniform distance metric and arbitrary curves in any dimension for the Frechet error measure under L p metrics. We present experimental results demonstrating that our algorithms are simple and fast, and produce close to optimal simplifications in practice.

Original languageEnglish (US)
Pages (from-to)203-219
Number of pages17
JournalAlgorithmica (New York)
Issue number3-4
StatePublished - Jun 2005


  • Approximation algorithms
  • Computational geometry
  • Curve simplification

ASJC Scopus subject areas

  • Computer Science(all)
  • Computer Science Applications
  • Applied Mathematics


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

Cite this