One question — which station is nearest to me — is enough to cut the plane into a mosaic. The border between two seeds is always the perpendicular bisector of the segment joining them, and since an intersection of half-planes is convex, every Voronoi cell is a convex polygon. Join the seeds that share an edge and you get the Delaunay triangulation, the dual structure with its empty-circumcircle property. Move each seed to the centroid of its own cell and repeat, and Lloyd’s relaxation pulls a ragged tiling toward a near-hexagonal lattice; that same procedure is k-means.
One question — which station is nearest to me — is enough to cut the plane into a mosaic. The border between two seeds is always the perpendicular bisector of the segment joining them, and since an intersection of half-planes is convex, every Voronoi cell is a convex polygon. Join the seeds that share an edge and you get the Delaunay triangulation, the dual structure with its empty-circumcircle property. Move each seed to the centroid of its own cell and repeat, and Lloyd’s relaxation pulls a ragged tiling toward a near-hexagonal lattice; that same procedure is k-means.
Related topics in Mathematics