覆盖区域的消防部门

Question

给定一组点（GPS坐标）和包含所有这些点的多边形，可以确定这些点覆盖区域的多么好，或者多边形内任何位置到该区域的最长距离最近的点是？例如，如果我拥有纽约市境内的所有消防部门，我想知道在最坏的情况下消防车必须驾驶多久（以防紧急情况发生）。

关于这个问题的名称是什么或者这个问题可以减少到什么的任何想法？或者是否有任何现有的算法？

谢谢:)

Answer 1

首先构建了一套网站的Voronoi diagram（GPS坐标）。 Voronoi图是一种数据结构，表示将平面划分为单元格，每个单元格为一个单元格，这样每个单元格的单元格就包含了与该网站相比其他任何网站更接近的所有点。

构建Voronoi图可以在O(nlog(n))使用Fortune's sweep-line algorithm完成，其中n是输入网站的数量。

然后迭代Voronoi单元。每个单元格都是一个多边形。对于每个单元格计算单元格的站点与每个多边形顶点之间的距离。站点与站点单元顶点之间的最长距离是人们为了到达站点而必须走的最长距离。

该算法的运行时间为O(nlog(n))作为该算法的第二阶段（遍历每个Voronoi单元的顶点）只需要线性时间。这是因为整个图中顶点的总数随着站点的数量而线性增长。也就是说，使用Euler's formula for planar graphs来显示Voronoi顶点的总数与2n-5之间的界限是不太难的。

您可以在网上找到一些Fortune算法的开源实现。例如This one。