沃羅諾伊圖

沃羅諾伊圖把平面分給一組稱為生成點的點：每個生成點擁有的區域，是到它的距離不大於到任何其他生成點距離的所有點。畫面是平面上的一扇窗，區域內的明暗只供視覺呈現。藍色探針是一個空圓的圓心，圓周碰到最近的生成點。在這裡，你可以移動生成點，觀察鄰居的區域如何改變；讓各區域從自己的生成點長出來；觀看德勞內三角剖分；也可以把生成點分布得更均勻，讓圖案接近蜂窩。

到生成點$p$的距離不大於到另一個生成點$q$距離的點，形成以$pq$中垂線為邊界的半平面。$p$的區域是這些半平面的交集，每個其他生成點對應一個半平面，因此區域是凸的。只有部分中垂線會成為邊。區域與$p$的區域共用一條邊的生成點，是它的鄰居；其餘半平面已經包含整個區域。畫框只是窗的邊界；區域延伸到無窮遠，若且唯若它的生成點位於所有生成點的凸包邊界上。

三個或更多區域相交的頂點，到各自生成點的距離相等，因此是通過這些生成點之圓的圓心。圓內沒有生成點：如果有，它到頂點的距離會更近，頂點就應該屬於它的區域。通常一個頂點恰好有三個區域相交。當恰好四個生成點位於同一個空圓上，例如正方形格點，就會有四個區域相交；隨機散布的生成點幾乎不會如此。

生長讓每個生成點以相同速率長出圓盤。每個位置都先被最近的生成點抵達，因此前緣恰好在邊上相遇。小圖從側面呈現同一個生長過程：每個位置的高度等於到最近生成點的距離，也就是立於各生成點上的圓錐$z = |x - s|$中最低的高度。山脊對應區域的邊，生長則像水位上升。最後淹沒的位置是畫框內地形的最高點，也就是圓心限於畫框內之最大空圓的圓心。

三角剖分連接區域共用一條邊的兩個生成點；當四個或更多生成點共用一個空圓，例如正方形格點，還會補上虛線對角線。只要生成點不全都共線，結果就是德勞內三角剖分。每個三角形的外接圓，就是以圖中一個頂點為圓心的空圓。

均勻化逐輪把每個生成點移到自己區域的質心，再重新劃分區域；區域先裁切至畫框內。這就是勞埃德演算法。小圖顯示畫框內一點到最近生成點的平均平方距離，再除以每個生成點分得的畫框面積。每一輪都不會讓這個值增加。生成點固定時，依最近生成點劃分區域可讓它最小；區域固定時，則是質心讓它最小。蜂窩線是一個下界，對應等大的正六邊形、生成點位於中心時的值。從散布的生成點出發，過程會停在附近的穩定狀態，而非完美蜂窩：通常仍有五邊形與七邊形相鄰，如同晶體中的差排。

沃羅諾伊圖以喬治・沃羅諾伊命名，他在1908年研究了任意維度的這類劃分；三角剖分則以鮑里斯・德勞內命名，他在1934年描述了它。