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.