我有一组 n 个点和一个或多或少的任意圆。
现在我想检查圆圈是否最多包含 k 个点。
现在我只是蛮力测试所有的点。由于我需要为很多圈子回答这个问题，因此最多 n²log(n) 的预处理时间就可以了。
最佳数据结构很可能是 k-Voronoi 图的顺序(不是 k 维的那个)，但我需要自己实现它，因此我想知道我是否有其他(更简单的)选项。
另一个加速的想法是使用 KD-Tree。
我想知道，如果我错过了另一种方法。
最佳答案
您似乎在进行固定半径的近邻计数查询。
使用 KD 树 (K=2)，您可以列出给定圆中的点，时间大约为 O(k + Log n)。这是通过将圆与 KD 树分割的矩形重叠来实现的。当一个矩形全部包含在圆内时，不需要再分割，矩形内的所有点都在圆内。
因此，您可以使用树的每个节点中包含的点数来增强树。这会将运行时间降低到 O(m + Log n)，其中 m 是包含在圆圈中或被圆圈分割的矩形的数量。当矩形包含的点数少于预定义数量时，也可以停止分割，并通过蛮力测试它们。
这些是启发式方法。你必须在你的案例上测试它们，看看它们是否值得。
更新:
只是一个想法，并没有真正研究过:Vantage-point 树适用于 k-最近邻搜索，它们使用圆来划分平面。这可能会更好地与圆查询融合。
https://en.wikipedia.org/wiki/Vantage-point_tree#Searching_through_a_vantage-point_tree
关于java - 检查任意圆是否包含给定点集的 k 个以上点，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/66247451/