Leonidas Guibas obtained his Ph.D. from Stanford under the supervision of Donald Knuth. His main subsequent employers were Xerox PARC, Stanford, MIT, and DEC/SRC. He has been at Stanford since 1984 and is currently the Paul Pigott Professor of Computer Science (and by courtesy, Electrical Engineering). He heads the Geometric Computation group and is part of the Graphics Laboratory, the AI Laboratory, the Bio-X Program, and the Institute for Computational and Mathematical Engineering. Professor Guibas' interests span computational geometry, geometric modeling, computer graphics, computer vision, robotics, ad hoc communication and sensor networks, and discrete algorithms --- all areas in which he has published and lectured extensively.
Some well-known past accomplishments include the analysis of double hashing, red-black trees, the quad-edge data structure, Voronoi-Delaunay algorithms, the Earth Mover's distance, Kinetic Data Structures (KDS), and Metropolis light transport. Professor Guibas is an ACM Fellow and a winner of the ACM Allen Newell award.
Title of Talk: Voronoi Diagrams in Geometry Processing and Network Routing
It is nearly 150 years since the birth of Georgy Voronoi -- and the applications of Voronoi diagrams do not cease to expand. In this talk I will start with some general remarks on the role that Voronoi diagrams have played in my own career and then focus on two recent developments which use Voronoi techniques in non-traditional settings. In the first part I cover the estimation of differential information, such as normals and curvature, in 3D point cloud data. I briefly discuss a method for recovering principal curvatures and principal curvature directions in smooth parts of a sampled shape, and correct feature directions and feature angles at the sharp edges of a piecewise smooth surface -- all with theoretical guarantees. The method is integral in nature and uses convolved covariance matrices of Voronoi cells of the point cloud, making it provably robust in the presence of noise. In the second part I cover an application of Voronoi diagrams to routing in sensor networks in which Voronoi techniques are used to provide names for the network nodes based on a chosen set of landmark nodes. Using these names a set of local coordinates is derived from connectivity graph distances and a gradient decent method is obtained for routing which guarantees packet delivery when the node density is sufficiently high -- showing that navigation is possible directly from distances to landmarks, without localization.