本文主要是介绍一个小问题引发的惨案（计算几何，Voronoi图，半平面交），对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

某天无聊，脑子里突然蹦出一个小问题：

给定一个矩形平面，有\(n\)个相同功率的通信基站，请在平面上求出信号最弱的位置

或者说，有\(n\)个点，找出一个位置，使其离这些点中最近的点最远

是不是一个很简单的小问题呢

引入Voronoi图，定义法

对于平面上每个位置，都能找到离其距离最近的一个点。反过来看，每个点都对应一个离它距离最近的位置集合。

我们需要求的答案位置，必是\(n\)个集合中离点最远的位置中最远的那一个

这个集合长啥样呢？

对于点\(i\)，枚举点\(j(1\le j\le n,i\ne j)\)，平面上到\(i\)比到\(j\)近的部分，是两点中垂线分割开，靠\(i\)近的一侧半平面

那么平面上到\(i\)比到其它点都近的部分，就是\(n-1\)个半平面与矩形的交，会是一个多边形，点\(i\)称为该多边形的基点

把所有\(n\)个多边形求出来，它就有了专业名称：Voronoi图，多边形称为泰森多边形（百度百科）

多边形的集合是整个平面的一个划分，这样的定义赋予了泰森多边形深刻的现实意义：假设设备都连到距离最近的基站上，那么每个多边形就是对应基站的服务区域

类似地，在地理学、天文学、结晶化学、城市规划等方面也有着切实的应用

至此我们也给出了构建Voronoi图的朴素算法：定义法，求\(n\)个半平面交，复杂度\(O(n^2\log n)\)

半平面交算法可参考蒟蒻的计算几何细节梳理&模板

引入Delaunay三角网，逐点插入法

Voronoi图是平面图，Delaunay三角网与它互为对偶图（对于Voronoi图的每条边，连接其相邻两个泰森多边形的基点）

这两者联系起来，有着许多奇妙的数学性质，这里只略提一二，方便后面算法的引入

一般情况下，Voronoi图的每个顶点与三条边相连，在Delaunay三角网中，周围的三个基点连成三角形，顶点是这个三角形的外接圆圆心（中垂线交点）

（暂不讨论特殊情况：Voronoi图的每个顶点与更多边相连，多个Delaunay三角形外接圆圆心重合）

由此引入Delaunay三角网的重要性质：对于其中任意一个三角形，其外接圆内部不包含任何一个基点（空圆性）

理由是这样，假如包含某个基点，那么外接圆圆心到这个基点的距离比那三个基点更小，应该被划分在这个基点的泰森多边形内，矛盾

了解这个性质，能够帮助我们理解Voronoi图的更高效算法，同时也是Delaunay三角剖分的标准算法：逐点插入法

其思想是维护\(n\)个点的Delaunay三角网，然后加入新点，通过局部调整，生成\(n+1\)个点的Delaunay三角网

分治法

扫描线法

问题变种

相关题目

更新中！

这篇关于一个小问题引发的惨案（计算几何，Voronoi图，半平面交）的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！