Correction to "A Linear-Time Algorithm for Triangulating Simple Polygons"

In "A linear-time algorithm for triangulating a simple polygon" [Proceedings of the Eighteenth Annual ACM Symposium on Theory of Computing (1986), 380-388. 486], the analysis showing that the authors' triangulation algorithm runs in linear time is incorrect, and indeed the algorithm does not run in linear time in the worst case. So far they have been unable to obtain a linear-time algorithm for the triangulation problem. They have been able to obtain an O(n loglogn)-time algorithm, however. The details are described in "An O(n loglogn)-Time Algorithm for Triangulating a Simple Polygon, " SIAM Journal on Computing 17, 1 (February, 1988), to appear.

Authors

• Robert Endre Tarjan
• Christopher J. Van Wyk

Keywords

• Computer science
• Algorithm design and analysis
• Linear Time