Department of Mathematics
 Search | Help | Login | pdf version | printable version

Math @ Duke



Publications [#235478] of Pankaj K. Agarwal

Papers Published

  1. Agarwal, PK; Har-Peled, S; Mustafa, NH; Wang, Y, Near-linear time approximation algorithms for curve simplification, Algorithmica (New York), vol. 42 no. 3-4 (2005), pp. 203-219 [doi]
    (last updated on 2018/02/23)

    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.
ph: 919.660.2800
fax: 919.660.2821

Mathematics Department
Duke University, Box 90320
Durham, NC 27708-0320