Voronoi-diagram
Een verdeling van het vlak in cellen, één per zaadpunt, waarbij elke cel alles bevat wat dichter bij dat punt ligt dan bij enig ander.
Genoemd naar Georgi Voronoi (1908), al had Descartes het idee eerder geschetst. Bij een verzameling zaadpunten wordt elke plek toegewezen aan het dichtstbijzijnde punt, waardoor de ruimte in convexe cellen uiteenvalt. Het diagram is de duale van de Delaunay-triangulatie: verbind zaden waarvan de cellen een rand delen, en de ene komt uit de andere voort.
Games leunen er voortdurend op: biome- en regiokaarten, scheur- en breukpatronen voor destructieve geometrie, procedurele texturen (Worley-ruis is niets anders dan Voronoi-afstand) en invloedskaarten. Het sweep-linealgoritme van Fortune berekent het in O(n log n).