Name
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 Lp metrics.
We present
experimental results demonstrating that our algorithms
are simple and fast, and produce close to optimal
simplifications in practice. |
Year | DOI | Venue |
|---|---|---|
2005 | 10.1007/s00453-005-1165-y | European Symposium on Algorithms |
Keywords | Field | DocType |
computational geometry,approximation algorithms.,curve simplification,linear time,distance metric | Hausdorff dimension,Approximation algorithm,Discrete mathematics,Combinatorics,Vertex (geometry),Round-off error,Computational geometry,Polygonal chain,Time complexity,Monotone polygon,Mathematics | Journal |
Volume | Issue | ISSN |
42 | 3-4 | 0178-4617 |
ISBN | Citations | PageRank |
3-540-44180-8 | 40 | 2.31 |
References | Authors | |
11 | 4 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Pankaj K. Agarwal | 1 | 5257 | 593.81 |
| Sariel Har-Peled | 2 | 2630 | 191.68 |
| Nabil H. Mustafa | 3 | 390 | 41.24 |
| Yusu Wang | 4 | 860 | 57.40 |