# Approximation algorithms for projective clustering

Published

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