脚本宝典收集整理的这篇文章主要介绍了一个小问题引发的惨案（计算几何，Voronoi图，半平面交），脚本宝典觉得挺不错的，现在分享给大家，也给大家做个参考。

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

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

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

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

引入Voronoi图，定义法

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

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

这个集合长啥样呢？

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

分治法

扫描线法

问题变种

相关题目

更新中！

脚本宝典总结

以上是脚本宝典为你收集整理的一个小问题引发的惨案（计算几何，Voronoi图，半平面交）全部内容，希望文章能够帮你解决一个小问题引发的惨案（计算几何，Voronoi图，半平面交）所遇到的问题。

如果觉得脚本宝典网站内容还不错，欢迎将脚本宝典推荐好友。

本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。