Voronoi diagram

Voronoi diagram is a partitioning of a plane into regions based on distance to points in a specific subset of the plane. That set of points (called seeds, sites, or generators) is specified beforehand, and for each seed there is a corresponding region consisting of all points closer to that seed than to any other. These regions are called Voronoi cells. Voronoi diagram is a technique of graph clustering (Polanco, 2013)

Voronoi diagram - Fortune algorithm (1986) animation in Wikipedia

References

Voronoi, Georgy (1908). "Nouvelles applications des paramètres continus à la théorie des formes quadratiques". Journal für die Reine und Angewandte Mathematik 133: 97–178.
Franz Aurenhammer (1991). Voronoi Diagrams – A Survey of a Fundamental Geometric Data Structure. ACM Computing Surveys, 23(3):345–405, 1991.
Steven Fortune. A sweepline algorithm for Voronoi diagrams. Proceedings of the second annual symposium on Computational geometry. Yorktown Heights, New York, United States, pp.313–322. 1986.
Fortune's algorithm (in Wikipedia)
See, Powerpoint detailing the algorithm (author: Raymond Hill).  For a PDF Raymond Hill presentation of the Voronoi Diagrams with Fortune's algorithm, here.