Lloyd’s Algorithm Given a set of points  Lloyd’s algorithm (or relaxation) repeatedly moves each point towards its associated Voronoi cell’s centroid The parameter ω  when > 1  allows faster convergence by over-relaxation