Colloquium Speaker

Pankaj K. Agarwal, Duke University
Geometric Approximation Using Core Sets
Date: Tuesday, May 3, 2005
Time: 11:00AM
Place: Gould-Simpson, Room 701
Refreshments will be served in the 7th floor lobby of Gould-Simpson at 10:45 AM


This talk presents a general technique for approximating the "extent'' of a set of points in d-dimensional space. Extent is an abstraction that includes as special cases the diameter, width, and smallest bounding box, ball, or cylinder. For a given tolerance epsilon>0, the technique computes a "core'' subset of the input points that approximates the extent of the whole set. The size of the core-set depends upon epsilon but is independent of the size of the input set, and for any fixed epsilon, the core-set can be computed in linear time. The technique extends to maintaining an approximation of the extent of moving points and to points given online in the streaming model. The technique also allows fitting various shapes, including spheres and cylinders, through a point set. Various extensions of this technique and open problems are also discussed.