April 26, 2011 - Nina Amenta

Title: The Voronoi Diagram of Points on a Surface: Surface, Medial Axis, and Complexity

Abstract:
The Voronoi diagram is a fundamental spatial data structure, used in data analysis and computer graphics to interpret clouds of points as meaningful shapes. An important example is when points are distributed on a lower-dimensional surface in space, for instance on the two-dimensional surface of an object in 3D-space. We will begin by describing how the Voronoi diagram of points on a surface can be used to approximate the surface and its skeleton (aka the medial axis). Then we'll talk about what is known, and more interestingly unknown, about the complexity of the Voronoi diagram of points on a surface. This will be a somewhat mathematical talk but with a lot of pictures and intuition.