包络算法优化-放置圆的最佳位置

我必须以最佳方式解决下列问题。

• 平面上N个点作为(x,y)对整数坐标给出
• 在同一平面上的M点,作为(x,y)对整数坐标表示圆的中心。所有这些圆的边上都有(0,0)。

点和圆的数量大约是100000个。用每一点检查每个圆的明显的解决方案具有O(n*m)的复杂性,并且具有100000个圆和100000个点,在具有64位SSE3单精度代码的核心2二重奏上需要大约15秒。与我竞争的引用实现使用相同的数据只需大约0.1秒。我知道参考实现是O(Nlog N+Mlog M)。

我想用以下方法优化我的算法。复制两份点数据,并按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)在圆之外,则以下不等式必须为真:

现在,如果我们把Rc从(1)代入(2),在我们做了一些简单的计算之后,我们得到:

• y>0的Yc<1/2y*(x^2+y^2)-Xc*x/y(3.1)

(3.1)和(3.2)对于从输入数据中选择的任何(x,y)的给定圆C(Xc,Yc)必须为真。

为了简单起见,我们做几个记号:

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

• y>0的所有点的Yc<MIN(E(Xc))(5.1)
• y<0的所有点的Yc>MAX(E(Xc))(5.2)

现在我不明白的部分来了。他们说,由于上述段落中所述的属性,我们可以在O(1)摊销时间中计算MIN()和MAX(),而不是使用包络算法计算O(N)时间。我不知道信封算法是怎么工作的。

有什么关于如何实现信封算法的提示吗?

编辑:

问题不在于数学意义上的信封是什么——我已经知道了。问题是如何在比O(n)更好的时间内确定包络线,显然可以在O(1)的摊销期内确定。

再次感谢!