Name
Abstract | ||
|---|---|---|
We consider the following two instances of the projective clustering problem: Given a set S of n points in Rd 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(klogk) strips of width at most w∗ that cover S. Its expected running time is O(nk2log4n) if k2logk⩽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(klogk) slabs of width at most w∗ can be computed in expected time O(n3/2k9/4polylog(n)). (iii) We compute a cover of S⊂Rd by O(dklogk) d-cylinders of diameter at most 8w∗ in expected time O(dnk3log4n). We also present a few extensions of this result. |
Year | DOI | Venue |
|---|---|---|
2003 | 10.1016/S0196-6774(02)00295-X | Journal of Algorithms |
DocType | Volume | Issue |
Journal | 46 | 2 |
ISSN | Citations | PageRank |
0196-6774 | 0 | 0.34 |
References | Authors | |
0 | 2 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Pankaj K. Agarwal | 1 | 5257 | 593.81 |
| Cecilia Magdalena Procopiuc | 2 | 0 | 0.34 |