Near-linear time approximation algorithms for curve simplification
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. © 2005 Springer Science+Business Media, Inc.
Agarwal, PK; Har-Peled, S; Mustafa, NH; Wang, Y
Volume / Issue
Start / End Page
International Standard Serial Number (ISSN)
Digital Object Identifier (DOI)