Approximation algorithms for projective clustering


Journal Article

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.

Full Text

Duke Authors

Cited Authors

  • Agarwal, PK; Procopiuc, CM

Published Date

  • January 1, 2003

Published In

Volume / Issue

  • 46 / 2

Start / End Page

  • 115 - 139

International Standard Serial Number (ISSN)

  • 0196-6774

Digital Object Identifier (DOI)

  • 10.1016/S0196-6774(02)00295-X

Citation Source

  • Scopus