快速计算圆内的点数

问题内容：

给定平面上的一组n个点，我想以某种方式比O（n ^ 2）（最好是O（nlog（n）））更快地预处理这些点，然后能够回答以下类型的查询“
n个点位于一个具有给定中心和半径的圆内？” 比O（n）更快（最好是O（log（n）））。

您能否建议一些可用于此问题的数据结构或算法？

我知道这类问题通常可以使用Voronoi图解决，但我不知道如何在此处应用。

问题答案：

建立空间细分结构，例如点的四叉树或KD树。在每个节点上存储该节点覆盖的点数。然后，当您需要计算查找圆所涵盖的点时，遍历该树，并针对节点中的每个细分检查其是否完全在圆的外部，然后忽略它，如果它完全在圆的内部，则将其计数添加到如果与圆相交，则总计，递归，当您到达叶子时，检查叶子内的点是否被包含。

这仍然是O（n）最坏的情况（例如，如果所有点都位于圆周长上），但平均情况是O（log（n））。