Computing And Using The Voronoi Diagram

Nina Amenta, University of California, Davis

Stevenson Hall 1300
11:00 AM - 11:50 AM

The Voronoi diagram of a set of points divides space into regions, each region consisting of the part of space closer to a particular input point p than to any other input point. It comes up in a wide variety of computational problems. In computer graphics, it is used to construct a polygonal surface given a set of point samples from the surface with no additional connectivity information -kind of a 3D connect-the-dots. This talk is about how the Voronoi diagram is computed, and how it can be used to solve this problem.