Geometric Approximation Using Coresets

Hamid Zarrabi-Zadeh

The coreset framework has recently attracted considerable attention as a powerful tool for approximating various measures of a geometric data set. In this framework, a small subset of the input, called a coreset, is extracted in such a way that solving the optimization problem on the coreset yields an approximate solution to the entire set.

In this talk, I will give a brief survey on the coreset technique and its application to geometric approximation. In particular, I will consider the problem of constructing geometric coresets in the data stream model (where points arrive one at a time), and present a new streaming algorithm that maintains an epsilon-coreset under the extent measure in near optimal space. This immediately improves the best previous streaming algorithms for a number of fundamental geometric optimization problems in fixed dimensions, including width, minimum enclosing cylinder, minimum bounding box, etc.