**Next:** Problem 25: Polyhedral Surface Approximation

**Previous:** Problem 23: Vertex \pi-Floodlights

- 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
- Categories
simplification

- Entry Revision History
J. O’Rourke, 2 Aug. 2001.

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