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

ABSTRACT

We present an algorithm for the 3-center problem in (ℝ^d, L_∞), i.e., for finding the smallest side length for 3 cubes that cover a given n-point set in ℝ^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 (ℝ^d, L₂), for any k ≥ 2. In particular, we prove that deciding whether a given n-point set in ℝ^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 alorithm for the latter does not exist, unless SNP ⊆ DTIME(2^o(n)).

REFERENCES

• 1: Pankaj K. Agarwal , Micha Sharir, Efficient algorithms for geometric optimization, ACM Computing Surveys (CSUR), v.30 n.4, p.412-458, Dec. 1998 [doi>10.1145/299917.299918]
• 2: E. Assa and M. J. Katz. 3-piercing of d-dimensional boxes and homothetic triangles. Int. J. Comput. Geometry Appl., 9(3):249--260, 1999.
• 3: T. M. Chan. Geometric applications of a randomized optimization technique. Discrete & Computational Geometry, 22(4):547--567, 1999.
• 4: Jianer Chen , Benny Chor , Mike Fellows , Xiuzhen Huang , David Juedes , Iyad A. Kanj , Ge Xia, Tight lower bounds for certain parameterized NP-hard problems, Information and Computation, v.201 n.2, p.216-231, September 15, 2005 [doi>10.1016/j.ic.2005.05.001]
• 5: R. Downey and M. Fellows. Parameterized Complexity. Springer-Verlag, 1999.
• 6: Z. Drezner. Facility Location. Springer-Verlag, 1995.
• 7: David Eppstein, Faster construction of planar two-centers, Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms, p.131-138, January 05-07, 1997, New Orleans, Louisiana, United States
• 8: J. Flum , M. Grohe, Parameterized Complexity Theory (Texts in Theoretical Computer Science. An EATCS Series), Springer-Verlag New York, Inc., Secaucus, NJ, 2006
• 9: R. J. Fowler, M. S. Paterson, and S. L. Tanimoto. Optimal packing and covering in the plane are NP-complete. Inf. Proc. Lett., 12(3):133--137, 1981.
• 10: Greg N. Frederickson , Donald B. Johnson, Erratum: generalized selection and ranking: sorted matrices, SIAM Journal on Computing, v.19 n.1, p.205-206, Feb. 1990 [doi>10.1137/0219013]
• 11: D. Marx. Efficient approximation schemes for geometric problems? In Proc. 13th Ann. European Sympos. Algorithms (ESA), volume 3669 of Lect. Notes Comput. Sci., pages 448--459. Springer-Verlag, 2005.
• 12: N. Megiddo, On the complexity of some geometric problems in unbounded dimension, Journal of Symbolic Computation, v.10 n.3-4, p.327-334, Sept./Oct. 1990 [doi>10.1016/S0747-7171(08)80067-3]
• 13: N. Megiddo and K. J. Supowit. On the complexity of some common geometric location problems. SIAM J. Comput., 13:182--196, 1984.
• 14: Micha Sharir , Emo Welzl, Rectilinear and polygonal p-piercing and p-center problems, Proceedings of the twelfth annual symposium on Computational geometry, p.122-132, May 24-26, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237218.237255]

INDEX TERMS

Keywords:
clustering, complexity, dimension, fixed-parameter tractability, lower bound