Speaker: Leonidas J. Guibas Stanford University
Time: 2007-05-31 14:30-2007-05-31 15:30
Venue: FIT Building 4-603, Tsinghua University

Abstract:

    Data sets consisting of points sampled from an underlying but hidden manifold arise in many areas of science and engineering. For example, in computer graphics digital models of real physical shapes are often based on 3D scanners, which deliver such point clouds. Large scale distributed simulations of protein motions, such as those of the folding@home project at Stanford, also yield large numbers of conformations which can be thought of as points in a high-dimensional shape space. We wish to infer properties of the underlying objects based on these samples, and reconstruct models of these objects with provable guarantees -- even though these samplings may be irregular, incomplete, have errors, and so on. The task is even more complicated because different aspects of the manifold may be visible only at different scales. Beyond analysis, we also wish to explore the use of such point-based representations as bone fide geometric and physical models of the underlying objects for further manipulation.
     This talk focuses on what can be done based on information obtained largely from distances between such samples (proximity information) -- ultimately allowing us to address these questions in the setting of general metric spaces, without any parametrization for the samples. We show that global aspects of the underlying manifold can be recovered in a multiscale fashion, such as its topology or its partial symmetries.
     Under certain sampling conditions, a geometric reconstruction is possible, with provable error bounds. Finally, we examine multiscale proximity structures which allow efficient updates under motion, useful for physical simulations of objects represented as point clouds. 
 

Short Bio:

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 as Professor of Computer Science, where he heads the Geometric Computation group within the Graphics Laboratory. He is also part of the AI Laboratory and the Bio-X Program. 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. At Stanford he has developed new courses in algorithms and data structures, geometric modeling, geometric algorithms, sensor networks, and biocomputation. Professor Guibas is an ACM Fellow.