Next: Problem 25: Polyhedral Surface Approximation
Previous: Problem 23: Vertex \pi-Floodlights
Can an n-vertex polygonal curve be simplified in time nearly linear in n?
Uncertain, pending investigation.
Open.
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].
simplification
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.