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.
Nina Amenta studies geometric algorithms, mostly in computer graphics. She is best-known for her research on surface reconstruction using the Voronoi diagram. She is also interested in biomedical visualization, particularly evolutionary morphology, and in using the GPU for problems involving spatial data. She received her PhD from the University of California at Berkeley in 1993. She was a post-doc at The Geometry Center and at Xerox PARC, and an Assistant Professor at the University of Texas at Austin, before moving to UC Davis in 2003. She is a recipient of an NSF CAREER Award, an Alfred P. Sloan Foundation Fellowship, and a UC Davis Chancellor’s Fellowship.