Clarification on K Means Clustering Algorithm and its Analysis I fail to understand how the circled point is assigned to cluster c2 and not c1. From what I have understood, the points are assigned to the (nearest?) centroid in order to minimise the squared distances i.e. to minimise the assignment cost.

Visually too, it appears to me that the circled point belongs to the first cluster. 

Please correct me if I'm wrong.

Source - http://www.cs.yale.edu/homes/el327/papers/OnlineKMeansAlenexEdoLiberty.pdf
K-means is an iterative algorithm. So what you have in the picture may be one of the early iterations and therefore the sum of squared distances (between points and clusters) has not been minimised yet. In further iterations, the circled point would indeed be assigned to cluster centroid C1.

Now, having said that, and this is purely speculation, but if the diagram in your picture is not simply 2 dimensional as we interpret it to be, but is actually a 2-d projection from a higher dimensional feature space, then indeed the circled point may be closer to centroid C2 in that higher dimensional space (although it doesn’t look like it in 2-d).