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?


Your proof makes no sense to me. I don't know what you mean by "each center is assigned to one of my centers". When writing a proof, you need to define all terms before first use, and use rigorous logic, where each step is logically implied by the prior step. You can't just write down some intuition that feels right; that's not a proof.

The claim is wrong. You are using Lloyd's k-means algorithm, but that is a heuristic not guaranteed to find the optimal answer.

If you are skeptical, try implementing your algorithm, implementing a brute-force algorithm to find the optimal answer (by trying all pairs of candidate centers), and test it on a million randomly generated testcases. I think you'll quickly discover that your algorithm doesn't always give the right answer.

  • $\begingroup$ Do you have some algorithm that works? I heard that it is possible to use Voronoi partitions... $\endgroup$ – Don Fanucci Jul 17 '17 at 4:48
  • $\begingroup$ @TrueTopologist, sure, I described an algorithm in the last paragraph. (There might be faster algorithms as well, but that one is certainly correct and runs in polynomial time.) $\endgroup$ – D.W. Jul 17 '17 at 6:20
  • $\begingroup$ I am sorry but in the first section you said that my proof is incorrect, in the second one you said that my algorithm is Lloyd's algorithm and in the last paragraph you only say that running my algorithm will show that it does not accomplish the optimal solution. I don't see an algorithm... $\endgroup$ – Don Fanucci Jul 17 '17 at 6:26
  • $\begingroup$ @TrueTopologist, read again the last paragraph, and note the part about "brute-force algorithm" and the parenthetical. $\endgroup$ – D.W. Jul 17 '17 at 6:27
  • $\begingroup$ 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$? $\endgroup$ – Don Fanucci Jul 17 '17 at 6:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.