java - 检查任意圆是否包含给定点集的 k 个以上的点

我有一组 n 个点和一个或多或少任意的圆。现在我想检查圆是否最多包含 k 个点。

现在我只是蛮力测试所有的点。由于我需要为很多圈子回答这个问题，因此最多 n²log(n) 的预处理时间就可以了。

最佳数据结构很可能是顺序 k-Voronoi 图（不是维度 k 的图），但我需要自己实现它，因此我想知道我是否还有其他（更简单的）选项。

另一个加快速度的想法是使用 KD-Tree。

我想知道，如果我错过了另一种方法。

标签： javacomputational-geometry

您似乎在进行固定半径近邻计数查询。

使用 KD-tree (K=2)，您可以列出给定圆中的点，时间大约为 O(k + Log n)。这是通过将圆与 KD-tree 细分的矩形重叠来实现的。当一个矩形完全包含在圆中时，不需要进一步细分，矩形内的所有点都在圆内。

因此，您可以使用树的每个节点中包含的点数来增强树。这会将运行时间降低到 O(m + Log n)，其中 m 是包含在圆中或被圆分割的矩形的数量。当一个矩形包含的点少于预定义的点数时，也可以停止细分，并通过蛮力测试它们。

这些是启发式的。你必须在你的案子上测试它们，看看它们是否值得。

更新：

只是一个想法，没有真正研究过：Vantage-point 树适用于 k 最近邻搜索，它们使用圆圈划分平面。这可能会更好地与圆形查询相结合。