Lloyd's algorithm 

There are several variations of Lloyd's algorithm. But all of them follow a common philosophy. 

For a given x_n (data point), the distance from the centroid µ in its cluster must be less than going to another center. Exactly like how a person in the lunch example wants to be closer to one table rather than having to go far to get a sandwich because of the crowd!

The best centroid µ for a given x_n is as follows:

This calculation is done for all µ (centroids) in all the clusters from k₁ to K.

Once each x_i has been allocated to a K_k, the algorithm recomputes µ by calculating the means of all the points that belong to each cluster and readjusts the centroid µ_k.