next up previous
Next: Problem 25: Polyhedral Surface Up: The Open Problems Project Previous: Problem 23: Vertex π-Floodlights


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(n4/3+ε) 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.



The Open Problems Project - December 04, 2015