我必须以最佳方式解决下列问题。
输入数据为：
平面上n个点作为（x，y）对整数坐标给出
在同一平面上的m点，作为（x，y）对整数坐标表示圆的中心。所有这些圆的边上都有（0，0）。
我需要找到一种方法来隔离一些圆，这些圆比任何一个“好”圆的性质都好，从前n个点开始，没有一个点位于所选圆或所选圆的边缘。
点和圆的数量大约是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）在圆之外，则以下不等式必须为真：
sqrt（（xc-x）^2+（yc-y）^2）>rc（2）
现在，如果我们把rc从（1）代入（2），在我们做了一些简单的计算之后，我们得到：
y>0时yc<1/2y*（x^2+y^2）-xc*x/y（3.1）
y1/2y*（x^2+y^2）-xc*x/y（3.2）
（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）
我们可以看到，对于给定的圆c（xc，yc），我们可以将（3）写成：
y>0的所有点ycymax（e（xc））（5.2）
我们可以看到e（xc）是相对于xc的线性函数，有两个参数——a（x，y）和b（x，y）。这意味着，基本上e（xc）在欧几里德空间中表示具有2个参数的直线族。
现在我不明白的部分来了。他们说，由于上述段落中所述的属性，我们可以在o（1）摊销时间中计算min（）和max（），而不是使用包络算法计算o（n）时间。我不知道信封算法是怎么工作的。
有什么关于如何实现信封算法的提示吗？
提前谢谢！
编辑：
问题不在于数学意义上的信封是什么——我已经知道了。问题是如何在比o（n）更好的时间内确定包络线，显然可以在o（1）的摊销期内确定。
我有一系列的函数，我需要计算包络线，我有一个数组，所有可能的参数。如何以最优化的方式解决最大化问题？
再次感谢！
最佳答案
这是Wikipedia entry on envelopes。这里有一个关于the envelope theorem in optimization的教程。