我必须以最佳方式解决以下问题。
输入数据是:
- 平面中的 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)
- Yc > MAX(E(Xc)) (5.2) 对于所有 y < 0 的点
我们可以看到 E(Xc) 是关于 Xc 的线性函数，有两个参数——A(x, y) 和 B(x, y)。这意味着基本上 E(Xc) 在欧几里德空间中表示具有 2 个参数的线族。
现在我不明白的部分来了。他们说，由于上一段中所述的属性，我们可以使用 Envelope 算法在 O(1) 分摊时间而不是 O(N) 时间内计算 MIN() 和 MAX()。我不知道信封算法如何工作。
关于如何实现信封算法的任何提示？
提前致谢!
编辑:
问题不在于数学意义上的包络是什么——我已经知道了。问题是如何在比 O(n) 更好的时间内确定包络，显然它可以在分摊的 O(1) 中完成。
我有计算包络线所需的函数族，并且有一个包含所有可能参数的数组。如何以最佳方式解决最大化问题？
再次感谢!
最佳答案
关于algorithm - 包络算法优化——放置圆圈的最佳位置，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/348005/