Approximation algorithms for projective clustering
We consider the following two instances of the projective clustering problem: Given a set S of n points in ℝd and an integer k > 0, cover S by k slabs (respectively d-cylinders) so that the maximum width of a slab (respectively the maximum diameter of a d-cylinder) is minimized. Let w* be the smallest value so that S can be covered by k slabs (respectively d-cylinders), each of width (respectively diameter) at most w*. This paper contains three main results: (i) For d = 2, we present a randomized algorithm that computes O(k log k) strips of width almost w* that cover S. Its expected running time is O(nk2log4n) if k2 log k ≤ n; for larger values of k, the expected running time is O(n2/3k8/3log14/3n). (ii) For d = 3, a cover of S by O(k log k) slabs of width at most w* can be computed in expected time O(n3/2k9/4 polylog(n)). (iii) We compute a cover of S ⊂ ℝd by O(dk log k) d-cylinders of diameter at most 8w* in expected time O(dnk3log4n). We also present a few extensions of this result. © 2003 Elsevier Science (USA). All rights reserved.
Agarwal, PK; Procopiuc, CM
Volume / Issue
Start / End Page
International Standard Serial Number (ISSN)
Digital Object Identifier (DOI)