沃羅諾伊圖（Voronoi diagram）
/ vuh-roh-NOY /
在一座城市裡散佈幾間郵局。對任一地址而言，哪一間郵局最近？若你按最近的郵局替地圖上每個點上色，城市便分裂成數個區域——每間郵局一塊領地，各自包含以該郵局為最近者的所有地方。這些領地的地圖就是沃羅諾伊圖。它是把空間切成一組站點周圍「勢力範圍」的自然方式。
精確地說，從一組稱為站點的有限點 P_1, P_2, ..., P_n 出發。站點 P_i 的沃羅諾伊胞是平面上所有離 P_i 比離任何其他站點都近的點所成的集合。這些胞分割整個平面（相等之處構成邊界）。兩個相鄰胞之間的邊界落在連接其兩站點之線段的垂直平分線上——即與兩者恰好等距的點所成的線——這正是為什麼每個胞都是凸多邊形，由直邊圍成。三個胞相遇之處，即沃羅諾伊頂點，該點同時與三個站點等距，所以它是通過這三者之圓的圓心。平面上 n 個站點建構此圖所需時間與 n log n 成正比，可用 Fortune 的掃描線演算法優雅地達成。
一旦你留意，沃羅諾伊圖無所不在：它模擬晶體如何生長、雨水往何處排、你的手機連到哪座基地台、生態學家如何劃分領域；它回答最近鄰查詢、驅動網格生成，並出現在藝術與建築中。它以沃羅諾伊（Georgy Voronoi）命名，但更早被狄利克雷使用，甚至約翰．斯諾（John Snow）在 1854 年繪製水泵周圍的霍亂死亡分布時也用過。一個誠實的提醒：此圖完全取決於所選的距離。熟悉的直線（歐氏）版本給出多邊形的胞，但換成不同的度量——比如城市街區距離，或依站點重要性加權的距離——胞的形狀便完全改變，有時邊界是彎曲的、甚至不連通。
只有兩個站點 A 與 B。沃羅諾伊圖就只是線段 AB 的垂直平分線：那單一條線把平面一分為二，離 A 較近的點在一側，離 B 較近的在另一側。加入第三個站點 C，便出現三條垂直平分線；它們相交於一點——與 A、B、C 等距——那正是三角形 ABC 的外心，即通過三個站點之圓的圓心。
每條胞邊界都是一條垂直平分線；三條垂直平分線交於一個外心。
沒有選定的距離，沃羅諾伊圖便毫無意義。人人想像中那乾淨的多邊形胞假設的是尋常的直線距離；改變度量，胞便可能彎曲、折轉、或徹底裂開。