Voronoidiagram
En uppdelning av planet i celler, en per utsådd punkt, där varje cell rymmer allt som ligger närmast just den punkten.
Uppkallat efter Georgy Voronoy (1908), även om Descartes skissat idén tidigare. Givet en mängd fröpunkter tilldelas varje plats sitt närmaste frö, och rummet styckas i konvexa celler. Diagrammet är dualen till Delaunay-trianguleringen: dra en linje mellan frön vars celler gränsar så faller det ena ut ur det andra.
Spel lutar sig mot det hela tiden — biom- och regionkartor, krack- och splittermönster för förstörbar geometri, procedurell textur (Worleybrus är just Voronoi-avstånd) och influenskartor. Fortunes svepealgoritm räknar ut det i O(n log n).