Title: Geometric Approximation Using Coresets: Old & New Results

Speaker:  Pankaj K. Agarwal
Duke University 

Date: Friday, Dec 14, 2007
Time 11:00-12:00PM
Venue: Room 3464, HKUST

 
Abstract:
The paradigm of coresets has recently emerged as a powerful tool
for developing fast approximation algorithms for geometric optimization
problems.  For a given tolerance, the technique computes a ``core''
subset of the input points that approximates an underlying measure of
the whole set.  It is shown that for a wide range of
interesting measures, the size of the coreset  depends upon
the approximation error but is independent of the size of the input set,
and the coreset can be computed efficiently.  Some of the
problems that have benefited from this approach including,
shape fitting, clustering, maintaining the extent of
moving points, maintaining geometric summaries of data
streams, and collision-free shortest paths. This talks gives
an overview of known results and discusses some of the open
problems.