给定平面上的一组 n 个点，我想以某种方式比 O(n^2)(最好是 O(nlog(n)))更快地预处理这些点，然后能够回答以下类型的查询“有多少n 个点位于具有给定中心和半径的圆内？”比 O(n) 快(最好是 O(log(n))。
你能建议一些我可以用来解决这个问题的数据结构或算法吗？
我知道这类问题通常可以使用 Voronoi 图来解决，但我不知道如何在这里应用它。
最佳答案
构建空间分割结构，例如点的 0x25181213341142 或 quadtree。在每个节点上存储该节点覆盖的点数。然后，当您需要计算查找圆覆盖的点数时，遍历树并为节点中的每个分割检查它是否完全在圆外，然后忽略它，如果它完全在圆内，则将其计数添加到总计，如果它与圆圈相交，则递归，当您到达叶子时，检查叶子内的点以进行遏制。
这仍然是 O(n) 最坏的情况(例如，如果所有点都位于圆的周长上)，但平均情况是 O(log(n))。
关于algorithm - 快速计算圆内的点数，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/1847310/