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)。