Polygonal Curve Simplification

Can an $n$ -vertex polygonal curve be simplified in time nearly linear in $n$ ?

Abstract

Given a polygonal curve and an error tolerance, compute a simplification using the fewest original vertices and ask whether an optimal solution is possible in nearly linear time.

Background and progress

A quadratic-time algorithm for optimal simplification is known [Chan and Chin, 1996]. For a particular error criterion, a subquadratic $O(n^{4/3+\varepsilon})$ algorithm was obtained [Agarwal and Varadarajan, 2000]; a nearly linear optimal algorithm remains open. The original problem appears in the Open Problems Project at https://topp.openproblem.net/p24.

Reference papers

Approximating polygonal curves by minimum number of line segments or minimum errorW. S. Chan, F. ChinInternational Journal of Computational Geometry and Applications · 1996
Efficient algorithms for approximating polygonal chainsPankaj K. Agarwal, Kasturi R. VaradarajanProceedings of the 16th Annual Symposium on Computational Geometry · 2000

Polygonal Curve Simplification

Coming soon

Organizer