一个小问题引发的惨案(计算几何,Voronoi图,半平面交)

2021/9/17 6:06:23

本文主要是介绍一个小问题引发的惨案(计算几何,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图,半平面交)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!


扫一扫关注最新编程教程