The Open Problems Project

Next: Problem 25: Polyhedral Surface Approximation

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