Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It only takes a minute to sign up.
Sign up to join this community
I want to divide a set of points into two equally-sized subsets such that the within-cluster sum of squares is minimized. We can assume that the points are in two-dimensional Euclidian space. I'm hoping for something faster than a general k-means clustering algorithm given that k=d=2. Can anyone point me in the direction of a good algorithm for this?
An exact solution not necessary if we have a good approximation.
Thanks!
If you insist on precise partition, then you need to compute all the balanced partitions of a set of points in the plane by a line (the optimal partition is a Voronoi partition, so the two point sets are separated by a line). Such partitions are known as $k$-sets. The fastest algorithm currently known for this work in $O(n^{4/3} \log n)$ for computing these partitions in the dual [i.e., the $k$-level of a set of $n$ lines, for $k=n/2$]. Once you have all the possible partitions, you just need to check each one of them. Using standard tricks, this can be done in constant time for each partition.
(Update: Proving that the optimal partition is realized by a $k$-set, for $k=n/2$, is not completely trivial. I would leave it as a cute exercise for the interested reader. Hint: Consider the line passing through the two optimal centers, and the direction perpendicular to it.)
If you do not care about the exact solution, then an easier approach would be to use a coreset for $k$-means clustering. This would result in $O( \epsilon^{-2} \log n)$ weighted points in this case, with total weight $n$. Then, you just need to solve the problem on the weighted point-set. The easiest solution would be to generate then a set of candidate locations for centers, and trying all pairs on the weighted points. The coreset construction, and generating the candidate centers is described in this paper:
