Lecture 12
Variations on Voronoi
Required Reading
Optional Reading
-
Chew, L. Paul. (1990). Building Voronoi diagrams for convex polygons in linear expected time. Technical Report PCS-TR90-147, Dept. Math. Comput. Sci., Dartmouth College, Hanover, NH.
-
Aggarwal, A., Guibas, L. J., Saxe, J., & Shor, P. W. (1989). A linear-time algorithm for computing the Voronoi diagram of a convex polygon. Discrete & Computational Geometry, 4(6), 591-604.