Next: Problem 25: Polyhedral Surface
Up: The Open Problems Project
Previous: Problem 23: Vertex πFloodlights
Problem 24: Polygonal Curve Simplification
 Statement
 Can an nvertex 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.
Quadratictime algorithms have been known for some time
[CC96] and a recent algorithm achieves time
O(n^{4/3+ε}) for a certain error
criterion [AV00]. In practice, the DouglasPeucker
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.
 AV00

P. K. Agarwal and Kasturi R. Varadarajan.
Efficient algorithms for approximating polygonal chains.
Discrete Comput. Geom., 23:273291, 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:5977, 1996.
 HS94

J. Hershberger and Jack Snoeyink.
An
O(n log n) implementation of the DouglasPeucker
algorithm for line simplification.
In Proc. 10th Annu. ACM Sympos. Comput. Geom., pages 383384,
1994.
 MO01

J. S. B. Mitchell and Joseph O'Rourke.
Computational geometry column 42.
Internat. J. Comput. Geom. Appl., 11(5):573582, 2001.
Also in SIGACT News 32(3):6372 (2001), Issue 120.
The Open Problems Project  September 19, 2017