想象一下，如果城市里所有超市的价格、商品、服务都一模一样，你会去哪家？当然是最近的那家。
把离同一家超市最近的所有位置连成一片，整张城市地图就被切成了一块块拼在一起的区域。这种按距离划分空间的方法，就是沃罗诺伊图（Voronoi diagram），以罗斯帝国(生于今乌克兰境内)格奥尔基·沃罗诺伊命名。
它的规则只有一条：对于空间中的任意一点，把它分配给距离最近的那个对象。
这套实用的划分区域的方法在不同领域被独立发现过好几次，所以名字也不止一个。数学上，德国的狄利克雷和沃罗诺伊先后建立和完善了理论，所以数学界称它为狄利克雷镶嵌或沃罗诺伊图。美国气象学家泰森为了估算降雨量，用每个气象站代表周边区域的降水，独立发明了同样的方法，所以地理和气象学领域则常叫它为泰森多边形。 平面上怎么划分unsetunset
先看最简单的情况：把每家超市看作平面上的一个点。
只有两家超市时，分界线就是两点连线的垂直平分线。超市多了，分界线也跟着变多，最后这些线把每家超市各自圈出一块区域。这些区域叫沃罗诺伊单元，对应到现实中，就是每家超市的服务范围。
这些区域有两个特点。第一，边界都是直的，而且不会向内凹，是凸的。第二，位置靠里的超市会被完全围住，形成封闭的凸多边形；位置靠外的超市，它的区域会向外无限延伸，没有外边界——就像城市边缘的超市，服务范围一直延伸到无限远的区域。
因为每一条边界都是一个半平面，而多个半平面的交集仍然是凸集，所以沃罗诺伊单元一定是凸多边形。
相邻两个区域的边界，是一条线段或射线，边界上任何一点到两家超市的距离都相等。三条以上边界交汇的顶点，则到周围几家超市的距离都一样。
unsetunset距离怎么算，是个前提unsetunset
上面所有的远近，都取决于距离这个概念怎么定义。不同的定义下，划分出来的区域形状也完全不同。所以谈空间划分之前，得先说清楚用的是哪种距离。
最常见的是平面直角坐标系中的直线距离(欧几里得距离)，两点 和 之间的直线距离用勾股定理就能算出来：
但在棋盘式的城市街区里，就不能走直线了，只能沿街道横竖行进。这时更实用的是曼哈顿距离：横向坐标差加纵向坐标差，就是实际要走的路程。
选用的距离度量不同，划分出的格子形态也会不同，如按曼哈顿距离划分如下图所示：
unsetunset对偶结构与实际应用unsetunset
在计算几何中，沃罗诺伊图和德劳内三角剖分（Delaunay triangulation）互为对偶：前者描述区域归属，后者描述点之间的连接关系。具体来说，只要两块沃罗诺伊区域共享一条边，就把对应的两个点连接起来；所有这些连线最终把整个平面划分成一系列三角形，这就是德劳内三角剖分。
更一般地，沃罗诺伊图的生成对象不一定是点，也可以是线段、曲线甚至多边形，因此它还能用于道路、河流等地理对象的空间划分。
沃罗诺伊图在实际应用中随处可见。比如，移动通信里的每个基站就可以看成一个点，它对应的区域就是信号覆盖范围，运营商可以据此调整基站位置，减少信号重叠和盲区。城市急救站的责任区划分也是同样的逻辑：让每个位置的急救呼叫都由最近的站点响应，以此来缩短救援时间。
自然界里也有现成的例子：玄武岩熔岩冷却收缩产生的裂隙，形态上和沃罗诺伊图高度相似，科学家也确实用它来给这类裂纹建模；蜻蜓翅膀的次级翅脉、植物细胞的排列，也都有类似的结构——甚至有研究认为，翅脉的生长过程本身就接近沃罗诺伊图的生成机制。
来源：遇见数学
编辑：endlesscliff
转载内容仅代表作者观点
不代表中科院物理所立场
如需转载请联系原公众号
热门跟贴