Voronoi diyagramı
Düzlemin, her tohum noktası için bir hücre olacak biçimde bölünmesi; her hücre o tohuma en yakın olan her şeyi içerir.
Adını Georgy Voronoy'dan (1908) alır, ancak fikrin ilk taslağını Descartes çizmişti. Bir tohum noktaları kümesi verildiğinde her konum en yakın tohuma atanır ve uzay dışbükey hücrelere ayrılır. Diyagram, Delaunay üçgenlemesinin dualidir: hücreleri bir kenar paylaşan tohumları birleştirirseniz biri ötekinden çıkar.
Oyunlar buna sürekli başvurur: biyom ve bölge haritaları, yıkılabilir geometri için çatlak ve parçalanma desenleri, prosedürel doku (Worley gürültüsü Voronoi mesafesinden başka bir şey değildir) ve etki haritaları. Fortune'un tarama çizgisi algoritması bunu O(n log n) sürede hesaplar.