Diagram Woronoja
Podział płaszczyzny na komórki, po jednej na punkt źródłowy, z których każda zawiera wszystko, co leży najbliżej tego punktu.
Nazwany od Gieorgija Woronoja (1908), choć Kartezjusz naszkicował tę ideę wcześniej. Dla zbioru punktów źródłowych każde miejsce jest przypisane do najbliższego z nich, co dzieli przestrzeń na wypukłe komórki. Diagram jest dualny do triangulacji Delaunaya: połącz punkty, których komórki mają wspólną krawędź, a jedno wynika z drugiego.
Gry sięgają po niego nieustannie — mapy biomów i regionów, wzory pęknięć i rozbicia w niszczalnej geometrii, tekstury proceduralne (szum Worleya to po prostu odległość Woronoja) i mapy wpływów. Algorytm zamiatania Fortune'a oblicza go w czasie O(n log n).