Problem 24: Polygonal Curve Simplification

Statement

Can an n-vertex polygonal curve be simplified in time nearly linear in n?

Origin

Uncertain, pending investigation.

Status/Conjectures

Open.

Partial and Related Results

The goal is to compute a simplification that uses the fewest vertices of the original curve while approximating it according to some prescribed error criterion. Quadratic-time algorithms have been known for some time [CC96] and a recent algorithm achieves time O(n^{4/3+$\epsilon$}) for a certain error criterion [AV00]. In practice, the Douglas-Peucker algorithm is often used as a heuristic; it can be implemented to run in time O(n log n) [HS94].

Appearances

[MO01]

Categories

simplification

Entry Revision History

J. O'Rourke, 2 Aug. 2001.

Bibliography

AV00

P. K. Agarwal and Kasturi R. Varadarajan.
Efficient algorithms for approximating polygonal chains.
Discrete Comput. Geom., 23:273-291, 2000.

CC96

W. S. Chan and F. Chin.
Approximation of polygonal curves with minimum number of line segments or minimum error.
Internat. J. Comput. Geom. Appl., 6:59-77, 1996.

HS94

J. Hershberger and Jack Snoeyink.
An O(n log n) implementation of the Douglas-Peucker algorithm for line simplification.
In Proc. 10th Annu. ACM Sympos. Comput. Geom., pages 383-384, 1994.

MO01

J. S. B. Mitchell and Joseph O'Rourke.
Computational geometry column 42.
Internat. J. Comput. Geom. Appl., 11(5):573-582, 2001.
Also in SIGACT News 32(3):63-72 (2001), Issue 120.