我必须以最佳方式解决以下问题。
输入数据为：
- 平面中的 N 个点，以 (x, y) 对整数坐标的形式给出
- M 点在同一平面上，以 (x, y) 对表示圆心的整数坐标给出。所有这些圆圈的边缘都有 (0, 0)。
我需要找到一种方法来隔离具有属性的多个圆，而不是对于任何“好”圆，前 N 个点中的任何点都不位于所选圆或所选圆的边缘。
点和圆的数量在 100,000 左右。用每个点检查每个圆的明显解决方案具有 O(N * M) 的复杂度，对于 100,000 个圆和 100,000 个点，在具有 64 位 SSE3 单精度代码的 Core 2 Duo 上大约需要 15 秒。我竞争的参考实现在相同的数据下只需要大约 0.1 秒。我知道参考实现是 O(Nlog N + Mlog M)。
我曾想过以下列方式优化我的算法。制作点数据的 2 个副本，并分别根据 x 坐标和 y 坐标对副本进行排序。然后仅使用位于由 [(xc - r, yc - r); 定义的正方形中的点。(xc + r, yc + r)]，其中 (xc, yc) 是“当前”圆的中心，半径为 r。我可以使用二分搜索找到该区间中的点，因为现在我使用已排序的数据。这种方法的复杂度应该是 O(Nlog N + Mlog^2 N)，确实比参考更快，但仍然明显慢。
我或多或少知道参考实现是如何工作的，但是有些步骤我不明白。我将尝试解释到目前为止我所知道的：
坐标为 (Xc, Yc) 的圆的半径为：
- Rc = sqrt(Xc * Xc + Yc * Yc) (1)
那是因为 (0, 0) 在圆的边缘。
对于点 P(x, y) 在圆外，以下不等式必须为真：
- sqrt((Xc - x)^2 + (Yc - y)^2) > Rc (2)
现在，如果我们将 (1) 中的 Rc 代入 (2)，然后在我们进行一些简单计算后将不等式平方，我们得到：
- Yc < 1/2y * (x^2 + y^2) - Xc * x/y (3.1) 对于 y > 0
- Yc > 1/2y * (x^2 + y^2) - Xc * x/y (3.2) 对于 y < 0
对于从输入数据中选择的任何 (x, y)，对于给定的圆 C(Xc, Yc)，(3.1) 和 (3.2) 必须为真。
为简单起见，让我们做一些符号：
- A(x, y) = 1/2y * (x^2 + y^2) (4.1)
- B(x, y) = -x/y (4.2)
- E(Xc) = 1/2y * (x^2 + y^2) - Xc * x/y = A(x, y) + Xc * B(x, y) (4.3)
我们可以看到，对于给定的圆 C(Xc, Yc)，我们可以将 (3) 写为：
- 对于 y > 0 的所有点，Yc < MIN(E(Xc)) (5.1)
- 对于 y < 0 的所有点，Yc > MAX(E(Xc)) (5.2)
我们可以看到 E(Xc) 是关于 Xc 的线性函数，具有 2 个参数 - A(x, y) 和 B(x, y)。这意味着基本上 E(Xc) 在欧几里得空间中表示具有 2 个参数的线族。
现在来了我不明白的部分。他们说，由于上一段中所述的属性，我们可以使用包络算法在 O(1) 分摊时间而不是 O(N) 时间内计算 MIN() 和 MAX()。我不知道信封算法如何工作。
关于如何实现信封算法的任何提示？
提前致谢！
编辑：
问题不在于数学意义上的信封是什么——我已经知道了。问题是如何在比 O(n) 更好的时间内确定包络，显然它可以在摊销 O(1) 中完成。
我有计算包络所需的一系列函数，并且我有一个包含所有可能参数的数组。如何以最佳方式解决最大化问题？
再次感谢！