1

我正在尝试提出一种算法来执行以下操作：

如果给定一组点，则为查询点找到不包含该组任何点的最大圆（以查询点为中心）。

到目前为止，我一直在考虑使用 Voronoi 图来查找包含最接近集合中某个站点点的点的区域（单元格），然后使用 Voronoi 中的边列表来构造梯形分解。从分解中我将能够找到查询点位于哪个单元格，然后圆的半径将是查询点到该单元格的点（站点）的距离。我认为创建这样的东西所需的存储是线性的，因为 Voronoi 需要 O(n) 存储，并且从 Voronoi 创建梯形分解也可以使用 O(n) 存储来完成。

*编辑：查询时间必须是 O(logn)，这意味着我不能一次遍历集合中的所有点。

这听起来对吗，还是我在这里遗漏了什么？

另外，如果有人有一些关于这个算法的参考资料，请告诉我。谢谢 ：）

4

2 回答 2

3

这个问题似乎是在询问从查询点到集合中最近点的距离，所以回答它的一种方法是找到最近的点。一种合理的标准方法是使用http://en.wikipedia.org/wiki/K-d_tree，这个问题一般在http://en.wikipedia.org/wiki/Nearest_neighbour_search

于 2012-06-08T04:29:14.437 回答
0

这听起来过于复杂。我什至不知道沃罗尼图是什么，但假设你的点都在一个二维平面上（这似乎是因为你提到了一个圆而不是一个球体），这是非常微不足道的：

遍历所有点，找到离查询点最近的点。这个距离就是勾股定理sqrt((point_x - query_x)^2 + (point_y - query_y)^2)。最小的距离是圆的半径。

于 2012-06-08T03:05:06.817 回答