Near-Linear Time Approximation Algorithms for Curve
Simplification

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

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 µ > 0, compute
a simplified polygonal curve P' whose error is less than
µ and size is at most the size of the optimal simplified
polygonal curve with error µ/2. We consider monotone
curves in the case of Hausdorff error measure and arbitrary curves
for the \Frechet error measure. We present experimental results
demonstrating that our algorithms are simple and fast, and produce
close to optimal simplifications in practice.