Summary: Let \(P\) be a set of \(n\) points in \(d\)-dimensional Euclidean space, where each of the points has integer coordinates from the range \([-\Delta, \Delta]\), for some \(\Delta \geq 2\). Let \(\varepsilon > 0\) be a given parameter. We show that there is subset \(Q\) of \(P\), whose size is polynomial in \((\log \Delta)/ \varepsilon\), such that for any \(k\) slabs that cover \(Q\), their \(\varepsilon\)-expansion covers \(P\). In this result, \(k\) and \(d\) are assumed to be constants. The set \(Q\) can also be computed efficiently, in time that is roughly \(n\) times the bound on the size of \(Q\). Besides yielding approximation algorithms that are linear in \(n\) and polynomial in \(\log\Delta\) for the \(k\)-slab cover problem, this result also yields small coresets and efficient algorithms for several other clustering problems.
For Part I by S. Har-Peled see Lect. Notes Comput. Sci. 3328, 324–335 (2004; Zbl 1117.68525).
For the entire collection see [Zbl 1099.68008].