The Open Problems Project

Next: Problem 25: Polyhedral Surface Approximation

Previous: Problem 23: Vertex \pi-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(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].





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


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.