FOCS Conference 1987 Conference Paper
Correction to "A Linear-Time Algorithm for Triangulating Simple Polygons"
- Robert Endre Tarjan
- Christopher J. Van Wyk
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.