Near-linear time approximation algorithms for curve simplification

Conference Paper

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.

Full Text

Duke Authors

Cited Authors

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

Published Date

  • January 1, 2002

Published In

Volume / Issue

  • 2461 /

Start / End Page

  • 29 - 41

Electronic International Standard Serial Number (EISSN)

  • 1611-3349

International Standard Serial Number (ISSN)

  • 0302-9743

International Standard Book Number 10 (ISBN-10)

  • 3540441808

International Standard Book Number 13 (ISBN-13)

  • 9783540441809

Digital Object Identifier (DOI)

  • 10.1007/3-540-45749-6_7

Citation Source

  • Scopus