沃羅諾伊圖（Voronoi diagram）
/ vuh-roh-NOY /
在一座城市裡撒下幾座消防站，問：對城裡每一點，哪座站最近？答案之圖把城市切成若干區域，每座站一個，每個區域就是離其站最近的領地。那個劃分就是沃羅諾伊圖。它是整個幾何中最自然的結構之一——自然界從細胞形狀、晶粒到長頸鹿的斑點，無處不用它。
形式上，給定平面（或 R^d）中帶距離的一組站點 P = {p_1, ..., p_n}，p_i 的沃羅諾伊胞腔是所有嚴格地離 p_i 比離任何其他站點更近之點的集合：V(p_i) = { x : d(x, p_i) <= d(x, p_j) 對所有 j }。這些胞腔是鋪滿整個空間的凸多邊形（在歐氏平面中）；它們共有的邊界是相鄰站點之間的垂直平分線——兩胞腔之間邊上的每一點到其兩個站點等距。圖的頂點是到三個或更多站點等距的點，即通過那些站點的空圓圓心。此圖正是德勞內三角剖分的幾何對偶：連接其胞腔相觸的兩個站點，就得到德勞內邊。它可用 Fortune 掃描線或經由抬升拋物面的凸包在 O(n log n) 內計算。
沃羅諾伊圖的應用無所不在：最近鄰查詢、設施選址、運動規劃（沿著邊走以盡量遠離障礙）、自然鄰居插值、網格生成，以及生物與材料中的生長建模。與德勞內的對偶意味著每個結構都能由另一個讀出，這是計算幾何中反覆出現的主題。誠實的告誡：外邊界（凸包）上站點的胞腔是無界的，延伸到無窮，穩健的實作必須特別處理；當站點移動越過共圓配置時，此圖不連續地改變；而「沃羅諾伊」預設了一個距離——換一個度量（曼哈頓，或加權／冪距離），胞腔未必是凸多邊形，且與德勞內乾淨的對偶會被修改。
只有兩個站點時，沃羅諾伊圖是一條線：連接它們之線段的垂直平分線，把平面分成兩個半平面（左邊的人都離左站點較近）。加入第三個站點，三條兩兩平分線交於一點——三角形的外心，到三者等距——它是一個沃羅諾伊頂點，也是那單一德勞內三角形的對偶。
沃羅諾伊邊是垂直平分線；一個頂點是到三個站點等距的外心。
沃羅諾伊與德勞內互為對偶，但作為資料並不可互換：凸包站點的胞腔無界、需要特別處理，而整個構造預設了一個度量。在非歐距離下（例如冪／加權沃羅諾伊），胞腔可能不再是凸多邊形，乾淨的德勞內對偶也被改動。