最小圆覆盖问题
给定一个\(n\)顶点的二维多边形,以每个顶点为圆心作一个半径为\(r\)的圆,记第\(i\)个顶点对应的圆覆盖的区域为\(R_i\)。求使得\(\bigcup_{i=1}^n R_i\)覆盖整个多边形内部区域的最小半径\(r^*\)。
图例
下图的半径\(r\)不足以覆盖多边形内部区域:
下图的半径\(r^*\)是足以覆盖多边形内部区域的最小半径:
解答
首先,该问题存在一个对半径\(r\)进行二分查找,并在多边形内进行采样以输出覆盖可行性的算法。该算法依赖一定的采样流程,难以求出精确的\(r^*\),效率也不高。下文将介绍用Voronoi图作为数据结构的高效算法。
记多边形的各顶点组成的集合为\(S = \{\mathbf p_1, \dots, \mathbf p_n\}\),多边形内部区域(包含边界)为\(P\),\(\mathbf p \in P\)是多边形内部的任意点。当\(r < r^*\)时,总存在\(\mathbf p\),满足\(\forall i, ||\mathbf p - \mathbf p_i|| > r\),即所有顶点对应的圆无法覆盖到该点。当\(r\)不断增大,直到当\(r = r^*\)时,上不等式对至少一个\(i\)取等,即存在临界点\(\mathbf q \in P\)恰好在第\(i\)个顶点的圆上,\(\exists i, ||\mathbf q - \mathbf p_i|| = r^*\),且对于其他\(j \neq i\)有\(||\mathbf q - \mathbf p_j|| \geq r^*\)。
容易发现,这样的临界点\(\mathbf q\)最大化了到\(S\)中各点的最小距离,且这个距离就是我们要求的\(r^*\)。考虑为\(S\)建立Voronoi图,并通过各生成点\(\mathbf p_i\)对应的Voronoi区域\(R^=(\mathbf p_i)\)对\(P\)进行区域划分,由此我们获得了多边形内的若干区域,如下图所示:
临界情况如下图所示:
那么,\(\mathbf p \in P\)到\(S\)中各点的最小距离完全由\(\mathbf p\)所处的Voronoi区域决定——若\(\mathbf p \in R^=(\mathbf p_i) \cap P\),则该距离的值为\(||\mathbf p_i - \mathbf p||\)。于是,我们只需枚举所有\(\mathbf p_i\),然后枚举区域\(R^=(\mathbf p_i) \cap P\)内的点,最大化\(||\mathbf p_i - \mathbf p||\)即可。
于是,我们将原问题转化为了如下的优化问题:
\[ \max_{i} z(\mathbf p_i) \ \ \ s.t. \begin{cases} z(\mathbf p_i) = \max_{\mathbf p}(||\mathbf p_i - \mathbf p||), \\ \mathbf p \in R^=(\mathbf p_i) \cap P. \end{cases} \]
对给定的\(\mathbf p_i\),如何最大化\(||\mathbf p_i - \mathbf p||\)?注意到区域\(R^=(\mathbf p_i) \cap P\)必然为多边形,可以用圆扩张的思想证明,一个多边形上的顶点\(\mathbf p_i\)与多边形内部(或边界)一点\(\mathbf p\)的最大距离,一定在\(\mathbf p\)位于多边形的(另一)顶点时取到。于是,我们不需要在二维区域\(R^=(\mathbf p_i) \cap P\)上枚举\(\mathbf p\),只需遍历有限的\(R^=(\mathbf p_i) \cap P\)的顶点,取最大化距离的\(\mathbf p\)即可。
于是,算法的步骤可以如下描述:
- 在多边形顶点集\(S\)上建立Voronoi图。
- 对多边形的每个顶点\(\mathbf p_i\),取多边形\(R^=(\mathbf p_i) \cap P\)的顶点集\(T_i\)。\(T_i\)中包含三种顶点:原多边形的顶点(也可忽略,不影响答案)、Voronoi点,以及原多边形的边与Voronoi边的交点。
- 遍历\(\mathbf p \in T\),计算\(||\mathbf p_i - \mathbf p||\);若计算结果大于当前最大值,则更新答案。若\(T_i\)遍历完毕,\(i = i + 1\)并回到步骤(2)。
可以证明,对给定的\(\mathbf p_i\),多边形\(R^=(\mathbf p_i) \cap P\)的顶点集\(T_i\)的平均规模为\(O(n)\),而原多边形顶点集\(S\)的规模为\(O(n)\),故算法的整体时间复杂度为\(O(n^2)\)。
更进一步地观察可以发现,临界点仅会在所有Voronoi点或原多边形的边与Voronoi边的交点上取到,因此可以直接枚举两种点:
- 枚举Voronoi点\(\mathbf p\)时,再枚举\(\mathbf p_i\),计算\(||\mathbf p_i - \mathbf p||\),更新答案,时间复杂度\(O(n^2)\)。
- 枚举原多边形的边与Voronoi边的交点时,计算交点花费\(O(n^2)\)时间;然后对每个交点\(\mathbf p\),取其所在Voronoi边垂直平分的\(S\)中顶点\(\mathbf p_i, \mathbf p_j\),计算\(||\mathbf p_i - \mathbf p||\)或\(||\mathbf p_j - \mathbf p||\),更新答案,花费\(O(1)\)时间。例如,图例中的临界点\(\mathbf q\)就是这样的点,只需计算其与\(\mathbf p_2\)或\(\mathbf p_3\)的距离即可。
算法整体时间复杂度仍为\(O(n^2)\),但简化了一些共享顶点的重复计算和求交流程。