# 2 means clustering

I had an exam in algorithms. The question stated:

Given $n$ points in the plane, find an algorithm that finds two centers (which can be any centers in the plane) such that the sum of the squares of the distances from the points is minimized. Prove your algorithm and analyse its complexity.

As I understood this question it is just a $2$-means problem in $\mathbb{R}^2$.

So I proposed the following algorithm:

1. Fix some partition of the points into two sets (clusters).
2. compute the centers of mass in each set (cluster), this are the new centers.
3. Assign each point to the correct center.
4. Go to 2 if some point changed its center.

In the proof section I proposed that if we look at the optimal solution it must be that each center is assigned to one of my centers so it must be also the center of mass in the cluster, thus my centers are the same as the optimal.

My teacher said it is false and reduced all the points, where is my mistake?

• Do you mean that a brute force algorithm will accomplish the optimal solution? By brute force here you mean trying every pair of points from the given $n$? – Don Fanucci Jul 17 '17 at 6:29