algorithm - 空圆查询算法

Question

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

如果给定了一组点，请为查询点找到最大的圆(以查询点为中心)，该圆不包含该组中的任何点。

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

*编辑:查询时间必须为 O(logn)，这意味着我无法一次遍历集合中的所有点。

这听起来对吗，还是我漏掉了什么？

此外，如果有人有一些我可以查看的有关此算法的引用资料，请告诉我。谢谢:)

Answer 1

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