Near-linear time approximation algorithms for curve simplification

Published

Journal Article

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.

Full Text

Duke Authors

Cited Authors

  • Agarwal, PK; Har-Peled, S; Mustafa, NH; Wang, Y

Published Date

  • June 1, 2005

Published In

Volume / Issue

  • 42 / 3-4

Start / End Page

  • 203 - 219

International Standard Serial Number (ISSN)

  • 0178-4617

Digital Object Identifier (DOI)

  • 10.1007/s00453-005-1165-y

Citation Source

  • Scopus