Next: Problem 25: Polyhedral Surface
Up: The Open Problems Project
Previous: Problem 23: Vertex π-Floodlights
Problem 24: Polygonal Curve Simplification
- Can an n-vertex polygonal curve be simplified
in time nearly linear in n?
- Uncertain, pending investigation.
- 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].
- Entry Revision History
- J. O'Rourke, 2 Aug. 2001.
P. K. Agarwal and Kasturi R. Varadarajan.
Efficient algorithms for approximating polygonal chains.
Discrete Comput. Geom., 23:273-291, 2000.
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.
J. Hershberger and Jack Snoeyink.
O(n log n) implementation of the Douglas-Peucker
algorithm for line simplification.
In Proc. 10th Annu. ACM Sympos. Comput. Geom., pages 383-384,
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 - September 19, 2017