Lecture 05
Polygon Triangulation
Required Reading
Optional Reading
-
Garey, M. R., Johnson, D. S., Preparata, F. P., & Tarjan, R. E. (1978). Triangulating a simple polygon. Inform. Process. Lett., 7, 175-179.
-
Lee, D. T., & Preparata, F. P. (1977). Location of a point in a planar subdivision and its applications. SIAM Journal on computing, 6(3), 594-606.
-
A particularly famous solution: Chazelle, B. (1991). Triangulating a simple polygon in linear time. Discrete & Computational Geometry, 6(3), 485-524.