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


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(6ddn log (dn)) 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].

  not the final revision: pdf file (gzipped)   free PDF @ACM
other papers about this subject
Last update: August 14, 2017.