如何在O(nlogn)中找到相交线的上包络线？

Question

免责声明:是的,这是一个家庭作业,我正在思考它几天但却找不到路要走.

所以有n条直线(y = ax + b),我想找到它们的上部包络线(图中的粗体部分).它必须在O(nlogn).

我的理解是,我需要找到一种方法来忽略一些行,因为如果我搜索所有行,它将不是O(nlogn).

我正在考虑分而治之的方法,以便我可以将列表分成两部分并递归地继续直到解决方案.但后来我不知道如何摆脱一些线路.很明显,我不需要考虑图片中的一些底线,因为他们不可能为解决方案做出贡献.但是我没有想到任何事情.任何提示都表示赞赏.

Answer 1

提示:这个问题基本上是凸壳问题的双重问题.

解决方案:如果您将每条线y=ax+b视为一个点(a,b),并添加一个额外的"点" (0, -infinity),您应该能够将其提供给任何2D凸包算法并获得正确的解决方案.

注意:相反,此问题的任何解决方案也可用于构建相同O()的2D凸包算法.

编辑:证明它的请求......

对于(x,y)高于特定线的点y=ax+b,您会有不等式ax - y + b > 0.

这个不等式也等于(-a,b)线上方的点(b)=x(-a)+y,其中x是斜率,y是截距.

这种二元性允许我们将点作为线和线处理为点:点和线上的任何证明或算法都可以映射到具有相反的线和点的同等有效的证明或算法.

在这种情况下:一组2D点的凸包确定了"极端"点,这些点不是其他点的凸起组合,以及连续极值点之间的线.相应地,凸包的双重版本确定那些不是其他凸起组合的"极端"线,以及连续极端线之间的交叉点.这是给定行集的包络.

凸包的双重性为您提供输入线组的上下包络.由于您只需要线条的上部包络线,因此需要添加低于任何可能的常规线条的线条以消除下部线条.或者,您可以查看解决方案并仅选择坡度增加的交叉点.

相反,该问题的任何解决方案都可用于确定一组点的上凸壳.运行两次,一次为行{(a,b)},再为行{(-a,-b)},将为您提供一个完整的凸包.

Answer 2

首先，我们为行构建两个不同的二叉搜索树，一个根据行排序，a另一个根据行排序b。

现在我们开始考虑lmin那些lmax具有最小和最大的线a；它们肯定会对与第二小和第二大线的交点给出的点做出贡献，我们将这两个点添加到上包络线中。

现在我们考虑和(xi,yi)之间的交点，并且理想情况下绘制垂直线。我们现在必须识别在坐标中相交的线，并从两棵树中删除所有这些线。lminlmaxx = xix = xiy0 s.t. y0 <= yi

我们如何识别这些线呢？b s.t. lmin <= b <= lmax我们使用第二棵树找到所有带有 a 的行。

最后我们还将把lmin和lmax从树上移除。

现在我们将递归获得的新树。