Home Bookmarks Papers Blog

No Coreset, No Cry

Sariel Har-Peled.

We show that coresets do not exist for the problem of 2-slabs in R3, thus demonstrating that the natural approach for solving approximately this problem efficiently is infeasible. On the positive side, for a point set P in R3, we describe a near linear time algorithm for computing a (1+µ)-approximation to the minimum width 2-slab cover of P. This is a first step in providing an efficient approximation algorithm for the problem of covering a point set with k-slabs.


Postscript, PDF.

Last modified: Tue Dec 14 23:50:56 CST 2004