北京
想象一下，如果城市里所有超市的價格、商品、服務都一模一樣，你會去哪家？當然是最近的那家。
把離同一家超市最近的所有位置連成一片，整張城市地圖就被切成了一塊塊拼在一起的區域。這種按距離劃分空間的方法，就是沃羅諾伊圖（Voronoi diagram），以羅斯帝國(生于今烏克蘭境內)格奧爾基·沃羅諾伊命名。
它的規則只有一條：對于空間中的任意一點，把它分配給距離最近的那個對象。
這套實用的劃分區域的方法在不同領域被獨立發現過好幾次，所以名字也不止一個。數學上，德國的狄利克雷和沃羅諾伊先后建立和完善了理論，所以數學界稱它為狄利克雷鑲嵌或沃羅諾伊圖。美國氣象學家泰森為了估算降雨量，用每個氣象站代表周邊區域的降水，獨立發明了同樣的方法，所以地理和氣象學領域則常叫它為泰森多邊形。 平面上怎么劃分unsetunset
先看最簡單的情況：把每家超市看作平面上的一個點。
只有兩家超市時，分界線就是兩點連線的垂直平分線。超市多了，分界線也跟著變多，最后這些線把每家超市各自圈出一塊區域。這些區域叫沃羅諾伊單元，對應到現實中，就是每家超市的服務范圍。
這些區域有兩個特點。第一，邊界都是直的，而且不會向內凹，是凸的。第二，位置靠里的超市會被完全圍住，形成封閉的凸多邊形；位置靠外的超市，它的區域會向外無限延伸，沒有外邊界——就像城市邊緣的超市，服務范圍一直延伸到無限遠的區域。
因為每一條邊界都是一個半平面，而多個半平面的交集仍然是凸集，所以沃羅諾伊單元一定是凸多邊形。
相鄰兩個區域的邊界，是一條線段或射線，邊界上任何一點到兩家超市的距離都相等。三條以上邊界交匯的頂點，則到周圍幾家超市的距離都一樣。
unsetunset距離怎么算，是個前提unsetunset
上面所有的遠近，都取決于距離這個概念怎么定義。不同的定義下，劃分出來的區域形狀也完全不同。所以談空間劃分之前，得先說清楚用的是哪種距離。
最常見的是平面直角坐標系中的直線距離(歐幾里得距離)，兩點 和 之間的直線距離用勾股定理就能算出來：
但在棋盤式的城市街區里，就不能走直線了，只能沿街道橫豎行進。這時更實用的是曼哈頓距離：橫向坐標差加縱向坐標差，就是實際要走的路程。
選用的距離度量不同，劃分出的格子形態也會不同，如按曼哈頓距離劃分如下圖所示：
unsetunset對偶結構與實際應用unsetunset
在計算幾何中，沃羅諾伊圖和德勞內三角剖分（Delaunay triangulation）互為對偶：前者描述區域歸屬，后者描述點之間的連接關系。具體來說，只要兩塊沃羅諾伊區域共享一條邊，就把對應的兩個點連接起來；所有這些連線最終把整個平面劃分成一系列三角形，這就是德勞內三角剖分。
更一般地，沃羅諾伊圖的生成對象不一定是點，也可以是線段、曲線甚至多邊形，因此它還能用于道路、河流等地理對象的空間劃分。
沃羅諾伊圖在實際應用中隨處可見。比如，移動通信里的每個基站就可以看成一個點，它對應的區域就是信號覆蓋范圍，運營商可以據此調整基站位置，減少信號重疊和盲區。城市急救站的責任區劃分也是同樣的邏輯：讓每個位置的急救呼叫都由最近的站點響應，以此來縮短救援時間。
自然界里也有現成的例子：玄武巖熔巖冷卻收縮產生的裂隙，形態上和沃羅諾伊圖高度相似，科學家也確實用它來給這類裂紋建模；蜻蜓翅膀的次級翅脈、植物細胞的排列，也都有類似的結構——甚至有研究認為，翅脈的生長過程本身就接近沃羅諾伊圖的生成機制。
來源：遇見數學
編輯：endlesscliff
轉載內容僅代表作者觀點
不代表中科院物理所立場
如需轉載請聯系原公眾號
特別聲明：以上內容(如有圖片或視頻亦包括在內)為自媒體平臺“網易號”用戶上傳并發布，本平臺僅提供信息存儲服務。
Notice: The content above (including the pictures and videos if any) is uploaded and posted by a user of NetEase Hao, which is a social media platform and only provides information storage services.
