检查任意圆是否包含超过给定点集的 k 个点

Checking if an arbitrary circle contains more than k points of a given pointset

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

现在我正在对所有要点进行强力测试。由于这个问题需要回答很多圈子，所以预处理时间最多n²log(n)就可以了。

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

另一个提高速度的想法是使用 KD 树。

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

看来你是在进行固定半径的近邻计数查询。

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

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

这些是启发式的。您必须在您的案例中测试它们，看看它们是否值得。

更新：

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