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
http://graphics.stanford.edu/ba-colloquium/
Abstract
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.
Contact: bac-coordinators@cs.stanford.edu
Back to the Colloquium Page