TY - GEN

T1 - Near-linear time approximation algorithms for curve simplification

AU - Agarwal, Pankaj K.

AU - Har-Peled, Sariel

AU - Mustafa, Nabil H.

AU - Wang, Yusu

N1 - Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 2002.

PY - 2002

Y1 - 2002

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=84938080619&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84938080619&partnerID=8YFLogxK

U2 - 10.1007/3-540-45749-6_7

DO - 10.1007/3-540-45749-6_7

M3 - Conference contribution

AN - SCOPUS:84938080619

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 29

EP - 41

BT - Algorithms - ESA 2002 - 10th Annual European Symposium, Proceedings

A2 - Möhring, Rolf

A2 - Raman, Rajeev

PB - Springer

T2 - 10th Annual European Symposium on Algorithms, ESA 2002

Y2 - 17 September 2002 through 21 September 2002

ER -