algorithm - 直线与凸集的交集

Question

设 X 是某个中等维空间中的 n 个点的集合 - 现在假设为 R^5。令 S 为 X 的凸包，令 p 为 S 中的一个点，令 v 为任意方向。最后，令 L = {p + lambda v : lambda a real number} 为沿方向 v 穿过 p 的直线。

我有兴趣找到一种合理有效的算法来计算 S 和 L 的交集。如果知道不存在这样的算法，我也很想知道!请注意，此交点可以由 L 与 S 的边界的(极端)两个交点表示。我特别感兴趣的是找到一种在 n 很大时表现良好的算法。

我应该说，在二维空间中很容易非常有效地做到这一点。在那种情况下，可以按照从 p 看到的“顺时针顺序”对 X 的点进行排序，然后进行二分查找。因此，初始排序需要 O(n log(n)) 步，然后进一步查找需要 O(log(n)) 步。我看不出更高维度的类似算法应该是什么。部分问题是二维凸体有 n 个顶点和 n 个面，而 3 维或更高维的凸体可以有 n 个顶点，但比 n 个面多得多。

Answer 1

您可以为此编写一个简单的线性程序。您希望根据 x + lambda v 位于输入点的凸包中的约束来最小化/最大化 lambda。 “位于的凸包中”是两点之间的坐标相等，其中之一是输入点的非负加权平均值，使得权重总和为 1。

作为一个实际问题，从少量随机选择的点开始，获得凸组合或不可行性证明，然后将不可行性证明解释为线性不等式并找到最违反的输入点可能是有用的它。如果您使用的是实用的求解器，这意味着您想要制定对偶，关闭一堆预求解的东西，然后使用无界证书将上面的内容基本上作为切割平面方法运行。除非您有病理数据，否则您很可能只需要告诉 LP 求解器您的一小部分输入点。