Geometric Clustering: Fixed-Parameter Tractability and Lower Bounds with Respect to the Dimension

We present an algorithm for the 3-center problem in (R-d, L-infinity),L- i.e., for finding the smallest side length for 3 cubes that cover a given n-point set in R-d, that runs in O(n log n) time for any fixed dimension d. 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 with the k-center problem in (R-d, L-2), for any k >= 2. In particular, we prove that deciding whether a given n-point set in R-d can be covered by the union of 2 balls of given radius is W[1]-hard with respect to d, and thus not fixed-parameter tractable unless FPT=W[1]. Our reduction also shows that even an O(n(o(d)))-time algorithm for the latter does not exist, unless SNP subset of DTIME(2(o(n))).