Math @ Duke

Publications [#235478] of Pankaj K. Agarwal
Papers Published
 Agarwal, PK; HarPeled, S; Mustafa, NH; Wang, Y, Nearlinear time approximation algorithms for curve simplification,
Algorithmica (New York), vol. 42 no. 34
(2005),
pp. 203219 [doi]
(last updated on 2018/02/23)
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 different error measures: Hausdorff and Frechet. For both error criteria, we present nearlinear 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.


dept@math.duke.edu
ph: 919.660.2800
fax: 919.660.2821
 
Mathematics Department
Duke University, Box 90320
Durham, NC 277080320

