Is there a fast k-means clustering for the special case in which k = 2 and the points are 2-dimensional? As the title asks: is there a fast (e.g., polynomial) algorithm to compute a 2-means clustering for a cloud of 2D points?
 A: Wikipedia says "If $k$ and $d$ (the dimension) are fixed, the problem can be exactly solved in time $O(n^{dk+1}\log{n})$, where $n$ is the number of entities to be clustered", citing the below. In your case, that would be $O(n^5\log{n})$.
Inaba, M., Katoh, N., & Imai, H. (1994). Applications of weighted Voronoi diagrams and randomization to variance-based $k$-clustering. Proceedings of 10th ACM Symposium on Computational Geometry. pp. 332–339. doi:10.1145/177424.178042
A: The usual k-means algorithms are O(nkd*i) where d is the dimensionality, and i the number of iterations. i is usually small, e.g. less than 100.
So from a theoretical complexity viewpoint, all common k-means algorithms are linear. So unless you believe the global optimum is at the same time (i) hard to find with random initialization, and (ii) essential for your application (usually, you do not need the optimum!) then just use a good implementation, rather than wasting time on a (non-linear) polynomial algorithm whose result often will not be much better anyway.
