# Geometric clustering: fixed-parameter tractability and lower bounds with
respect to the dimension

## 1. Sergio Cabello, Panos Giannopoulos, Christian Knauer, and Günter
Rote:

In: *Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete
Algorithms (SODA)*, San Francisco, January 2008, pp. 836–843. doi:10.1145/1347082.1347174

preliminary version without the hardness result for covering by 4
unit cubes
## 2. Sergio Cabello, Panos Giannopoulos, Christian Knauer, Dániel Marx, and
Günter Rote:

*ACM Transactions on Algorithms* **7** (2011),
Article 43, 27 pages. doi:10.1145/2000807.2000811
### Abstract

We present an algorithm for finding the smallest side length for 3
axis-aligned cubes that cover a given `n`-point set in `d`
dimensions in
`O`(6^{d}`d``n`
log (`d``n`)) time. This shows that the
problem is fixed-parameter tractable when parameterized with `d`.
On the other hand, using tools from parameterized complexity theory, we
show that this is unlikely to be the case for 4 cubes, and with the
`k`-center problem in the Euclidean metric, for any `k`>1.
In particular, we prove that deciding whether a given `d`-dimensional
set of `n` points can be covered by the union of 2 balls of given
radius, or by 4 axis-aligned cubes of given side length, is W[1]-hard with
respect to `d`, and thus not fixed-parameter tractable unless FPT=W[1].

Last update: August 14, 2017.