Voronoi diyagramı

Bir Voronoi diyagramı, düzlemi üreteç adı verilen bir nokta kümesi arasında paylaştırır: her üretecin bölgesi, o üretece en az diğer bütün üreteçlere olduğu kadar yakın noktalardan oluşur. Resim, düzleme açılan bir penceredir; bölgelerin içindeki gölgelendirme yalnızca görsel amaçlıdır. Mavi sonda, en yakın üretece kadar uzanan boş bir çemberin merkezidir. Burada üreteçleri taşıyıp komşularının bölgelerinin değişmesini izleyebilir, her bölgeyi kendi üretecinden büyütebilir, Delaunay üçgenlemesini görebilir ve üreteçleri bir peteğe yaklaşacak biçimde dengeleyebilirsin.

Bir $p$ üretecine, başka bir $q$ üretecine olduğundan daha uzak olmayan noktalar, sınırı $pq$ doğru parçasının orta dikmesi olan bir yarı düzlem oluşturur. $p$ üretecinin bölgesi, diğer her üreteç için bir tane olan bu yarı düzlemlerin kesişimidir; dolayısıyla dışbükeydir. Orta dikmelerin yalnızca bazıları kenara dönüşür. Bölgeleri $p$ üretecinin bölgesiyle bir kenar paylaşan üreteçler onun komşularıdır; diğer yarı düzlemler zaten bölgenin tamamını içerir. Çerçeve yalnızca pencereyi sınırlar. Bir bölge, ancak ve ancak üreteci bütün üreteçlerin dışbükey kılıfının sınırında yer alıyorsa sonsuza uzanır.

Üç veya daha fazla bölgenin buluştuğu köşe, bu bölgelerin üreteçlerine eşit uzaklıktadır; dolayısıyla onlardan geçen bir çemberin merkezidir. Çemberin içinde üreteç yoktur: olsaydı köşeye daha yakın olur ve köşe o üretecin bölgesine ait olurdu. Genellikle bir köşede tam üç bölge buluşur. Kare ızgaradaki gibi tam dört üreteç bir boş çember üzerinde olduğunda dört bölge buluşur; rastgele saçılmış üreteçlerde bu neredeyse hiç olmaz.

Büyüt, her üreteçten aynı hızla bir disk büyütür. Her noktaya önce en yakın üreteç ulaşır; bu yüzden cepheler tam kenarlar üzerinde buluşur. Küçük görünüm aynı büyümeyi yandan gösterir. Her noktanın üzerinde en yakın üretece uzaklığı kadar bir yükseklik oluşturur: üreteçlerin üzerinde yükselen $z = |x - s|$ konilerinin en düşük yüksekliği. Sırtlar kenarlardır, büyüme ise yükselen sudur. En son su altında kalan yer, çerçevedeki arazinin en yüksek noktasıdır; merkezi çerçevede olan en büyük boş çemberin merkezidir.

Üçgenleme, bölgeleri bir kenar paylaştığında iki üreteci birleştirir; kare ızgaradaki gibi dört veya daha fazla üreteç aynı boş çemberdeyse kesikli köşegenler ekler. Bütün üreteçler aynı doğru üzerinde değilse sonuç Delaunay üçgenlemesidir. Her üçgenin çevrel çemberi, diyagramın bir köşesi etrafındaki boş çemberdir.

Dengele, her üreteci çerçeveyle kesilmiş bölgesinin ağırlık merkezine taşır ve bölgeleri tur tur yeniden oluşturur. Bu, Lloyd algoritmasıdır. Küçük grafik, çerçevedeki bir noktanın en yakın üretece uzaklığının karesinin ortalamasını, üreteç başına çerçeve alanına bölerek gösterir. Hiçbir tur bu değeri artıramaz. Üreteçler sabitken en yakın üretece ait bölgeler, bölgeler sabitken ağırlık merkezleri değeri en aza indirir. Petek çizgisi bir alt sınırdır: merkezlerinde üreteç bulunan eşit düzgün altıgenlerin değeri. Dağınık üreteçlerden başlayan süreç, kusursuz bir petekte değil yakındaki bir dengede durur. Genellikle, kristaldeki dislokasyonlar gibi yan yana beşgenler ve yedigenler kalır.

Diyagram, 1908’de her boyutta bu tür bölünmeleri inceleyen Georgy Voronoy’un; üçgenleme ise 1934’te onu tanımlayan Boris Delaunay’ın adını taşır.