geometry - 这可以用 O(n) 中的线扫描算法解决吗？

Question

在这个问题中，给定平面中的 n 个水平线段，在 O(n) 时间内找到一条与所有线段相交并具有最大可能斜率的线，或者确定不存在这样的线。

我想过通过求解不等式并获得所有可能的线方程来找到所有可能的线，然后找到具有最大斜率的线，但是我找不到与我们在计算几何中学到的任何东西相关的解决方案谁能给我一个提示或提及计算几何中可能有帮助的任何相关主题

标签： geometrycomputational-geometryintersectionsegment

Answer 1

不，这个问题不能通过线性时间的线扫描算法解决 - 请参阅@YvesDaoust 评论。但是，它可以通过另一种方法在线性时间内解决 - 请参见下文。

您通过不等式n描述线段和刺线之间的交叉点的意图是正确的，但是您可以更进一步，将您的问题简化为具有两个变量和约束的线性规划 (LP) 问题。2*n

i让我们用三个数字 -xMin(i)和来表示段xMax(i)的参数y(i)。刺线将由等式描述y = a*x + b。这条线必须与线段相交i，因此对于每个这样的线段，我们有两个不等式，保证了相交：

a*xMin(i) + b <= y(i)
a*xMax(i) + b >= y(i)

因此，您需要在上述约束条件下最大化斜率a，2*n这是一个众所周知的具有两个变量a和的固定维度 LP 问题b。根据Nimrod Megiddo 的这篇论文n，可以及时解决具有约束和固定（不取决于n）变量数量的LP 问题O(n)。