The planar \(k\)-means problem is NP-hard (Q441888)

The authors prove the NP-hardness of the decision problem associated with the following optimization problem: given a set of points in the plane and a positive integer \(k\), find a set of \(k\) centres so as to minimize the sum of the distances between each point and its nearest centre. Here the distance between two points is defined as the square of their Euclidean distance. In a generalization of this problem, the \(k\)-means problem, the input points are allowed to be in a Euclidean space with arbitrary dimension. The \(k\)-means problem is a very natural clustering problem and it has been studied immensely in machine learning and algorithm communities (see the references in the paper). It had been known that the general problem is NP-hard, and that if both the dimension and the number of centres are fixed, then a polynomial time algorithm exists. This paper resolves the case in which the dimension is fixed but the number of centres is part of the input. The proof uses a complicated reduction from the planar 3-SAT problem to the planar \(k\)-means problem.