No Coreset, No Cry: II

摘要

Let P be a set of n points in d-dimensional Euclidean space, where each of the points has integer coordinates from the range [-Δ, Δ], for some Δ ≥ 2. Let ε > 0 be a given parameter. We show that there is subset Q of P, whose size is polynomial in (log Δ)/ε, such that for any k slabs that cover Q, their ε-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 Δ for the k-slab cover problem, this result also yields small coresets and efficient algorithms for several other clustering problems.