Broad Area Colloquium For AI-Geometry-Graphics-Robotics-Vision
(CS 528)

Geometric Approximation Using Coresets

Pankaj Agarwal, Duke University
January 10, 2005, 4:15PM
TCSeq 200


The paradigm of coresets has recently emerged as a powerful tool for efficiently approximating various extent measures of a point set. Extent is an abstraction that includes as special cases the diameter, width, and smallest bounding box, ball, or cylinder. For a given tolerance, the technique computes a ``core'' subset of the input points that approximates the extent of the whole set. It is shown that for a wide range of interesting measures, the size of the coreset depends upon epsilon but is independent of the size of the input set, and for any fixed tolerance, the coreset can be computed in linear time. The technique extends to maintaining an approximation of the extent of moving points and of points given online in the streaming model. The technique also allows fitting various shapes and for clustering. Various extensions of this technique and open problems are also discussed.

About the Speaker

Dr. Agarwal earned his PhD in Computer Science from the Courant Institute of Mathematical Sciences at New York University. He joined the Department of Computer Science of Duke University in 1989 where he is now the Chair and Earl D. McLean, Jr., Professor of Computer Science and Professor of Mathematics. His research interests include geometric algorithms and data structures, computational molecular biology, spatial databases, global change, geographic information systems, and robotics. He has authored four books and more than 200 scholarly articles in various journals, edited volumes, and international conferences. He has received many awards, including Sloan Fellow and ACM Fellow, and he serves on the editorial boards of a number of journals.


Back to the Colloquium Page