## 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 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.

Original language | English (US) |
---|---|

Pages (from-to) | 203-219 |

Number of pages | 17 |

Journal | Algorithmica (New York) |

Volume | 42 |

Issue number | 3-4 |

DOIs | |

State | Published - Jun 1 2005 |

## Keywords

- Approximation algorithms
- Computational geometry
- Curve simplification

## ASJC Scopus subject areas

- Computer Science(all)
- Computer Science Applications
- Applied Mathematics