algorithm - 给定许多圆和一个点，如何找到哪个圆包含该点

Question

我最近遇到了一个类似这样的问题

There are N disjoint (such that they do not touch or intersect) circles given by their center and radius, i.e. center = (x_i, y_i), radius = r_i. Then we have Q queries where a point (x, y) is given. For each query we need to find out the index i of the circle which contains that given point (-1 if no circle).
The constraints are roughly 1 <= N <= 10^5 and 1 <= Q <= 10^5. So a O(Q * log(N)) might be needed.

除了直截了当的O(Q * N)解决方案我能想到的唯一更好的方法是将圆圈的最左边和最右边的点保留为数组中的间隔，然后进行二进制搜索以找出包含该点的 x 坐标的间隔，但可能有多个间隔重叠并且不止一个圆可能包含该点。所以我不确定这是否行得通。

任何帮助将不胜感激。谢谢。

Answer 1

这可以解决为 nearest-neighbour query在 N+1 个维度。

想象一组在 3d 中具有固定半径的球，它们与平面 z=0 的交点恰好是您的一组圆。 (球可能相交，没关系)。现在，落入圆中的点必然比所有其他球的中心更靠近其对应球的中心。

最近邻问题得到了很好的研究。空间分区技术适用于现实生活中的数据，但最坏情况下的性能并不是很好。

编辑:由于查询点在固定平面 z=0 中，该问题可以看作是具有非欧几里德距离函数的二维最近邻问题。查询点到圆心的有效距离为

D = &sqrt;(d^2+R2 - r2)

其中 d 是实际距离，R 是球半径(所有球通用)，r 是圆半径。

解决这个问题的另一种方法是构建一个 power diagram圈子的集合。功率图是平面分割。有一些方法可以有效地回答“给定点属于平面分割的哪个单元格”形式的查询，例如，使用 Kirkpatrik's point location data structure .

这两种方法即使不等价，也很相似，因为在幂图中，点相对于圆的幂是距离公式中 D 的平方(R=0)。