algorithm - 径向扫描的实现

Question

你在二维平面上给定了 N 个点，我需要找出至少包含 M 个点的圆的最小半径。

我正在使用的方法:-

我将对圆的半径进行二分查找。

从给定的集合中选取一个任意点 P。我们使用 P 作为“旋转轴”(按照惯例，逆时针方向)旋转一个半径为 R 的圆 C，即我们在旋转过程中随时保持 C 接触 P。在旋转 C 的同时，我们维护一个计数器来计算 C 包围的点数。

请注意，只有当某个点 Q 进入(或离开)圆 C 的区域时，此计数器才会发生变化。我们的目标是提出一种算法，当其他点 Q ≠ 时，该算法将增加(或减少)此计数器P 进入(或离开)C 的区域。

(旋转)圆 C 的状态可以用单个参数 θθ 来描述，其中 (r,θ) 是圆 C 中心的极坐标，如果我们选择 P 作为极坐标的固定点坐标系。在这个系统中，旋转 C 意味着增加 θ。

对于每个其他点 Q(≠ P)，我们实际上可以计算 C 覆盖 Q 的 θ 范围。更正式地说，只要 (iff) θ∈[α,β]，C 就包含 Q。

所以，到目前为止，原始问题已经简化为:

在最多[α,β]区间内的最优θ值是多少？

简化后的问题可以用相当标准的 O(NlogN) 算法来解决。[3]这个减少的问题必须解决 N 次(每个点 P 一次)，因此时间复杂度为 O(N2logN)。

我能够知道如何执行此步骤:

对于每个其他点 Q(≠ P)，我们实际上可以计算 C 覆盖 Q 的 θ 范围。更正式地说，只要 (iff) θ∈[α,β]，C 就包含 Q。 所以，到目前为止，原来的问题已经简化为: 位于最多[α,β]区间的θ的最优值是多少？

能否请您建议如何实现该部分。

Answer 1

当Q进入或离开圆C(半径为R)时:

• P 和 C 的中心之间的距离是 R(因为它始终是)；和

• Q和C的中心距离也是R

所以，如果你绕Q画一个半径为R的圆，又绕P画一个半径为R的圆，它们相交的两点就是Q进入或离开时C的圆心。

令 ±θ 为 C 的中心与直线 PQ 之间的角度。如果将其画出，您可以很容易地看到 |PQ|/2R = cos(θ)，这使得您很容易找到您要寻找的角度。