Home Bookmarks Papers Blog

Geometric Approximation via Coresets - Survey

Pankaj K. Agarwal, Sariel Har-Peled and Kasturi R. Varadarajan.

The paradigm of coresets has recently emerged as a powerful tool for efficiently approximating various extent measures of a point set P. Using this paradigm, one quickly computes a small subset Q of P, called a \em coreset , that approximates the original set P and and then solves the problem on Q using a relatively inefficient algorithm. The solution for Q is then translated to an approximate solution to the original point set P. This paper describes the ways in which this paradigm has been successfully applied to various optimization and extent measure problems.

Postscript, PDF.

Last modified: Thu Oct 28 11:17:58 CDT 2004