Diagramma di Voronoi
Una partizione del piano in celle, una per ogni punto seme, in cui ciascuna cella contiene tutto ciò che è più vicino a quel seme.
Prende il nome da Georgij Voronoj (1908), anche se Cartesio ne aveva già abbozzato l'idea. Dato un insieme di punti seme, ogni posizione viene assegnata al seme più vicino, suddividendo lo spazio in celle convesse. Il diagramma è il duale della triangolazione di Delaunay: collegando i semi le cui celle condividono un lato, l'una discende dall'altro.
I giochi lo usano di continuo: mappe di biomi e regioni, schemi di crepe e frammentazione per la geometria distruttibile, texture procedurali (il rumore di Worley è semplicemente la distanza di Voronoi) e mappe d'influenza. L'algoritmo a sweep line di Fortune lo calcola in O(n log n).