r - 算法相交多面体和半线

Question

我正在寻找 R 中的一种算法，用于将凸多胞形与线段相交。我在这里找到了几篇关于平面堆栈交换的帖子，但我想知道这种算法是否存在于更高的维度中。我的谷歌搜索并没有真正产生很多答案。

线段由凸多胞形内部的一个点和外部的一个点组成。 R 中是否有可用的算法可以在维度 N<=10 中执行此操作？或者有人知道引用资料以便我可以自己实现算法吗？是否有关于寻找多胞形和交集的复杂性的信息？

Answer 1

对于计算几何中的问题，维度 d > 3 通常也可以是任意的 d。如果您将多面体作为相交半空间的集合，那么可能唯一明智的做法是将线段与每个分离超平面相交(通过求解 d 线性方程组)和采取离内部点最近的交叉路口。

如果您只有多面体的顶点，或者甚至只有一组顶点，其凸闭包是多面体，那么给定 R 库的最简单方法可能是线性规划。 (可以想象，您可以使用一种算法来计算小平面以找到高维凸包，但它们可能有 Theta(n^floor(d/2))，其中 n 是顶点数。)我不熟悉 R 中的 LP 求解器，所以我会用数学方式写下程序。翻译起来应该不会太难。设 p_0 为外部点，p_1 为内部点，v_i 为定义多胞形的第 i 个点.

maximize alpha_0
subject to

for 1 <= j <= d,
    p_0[j] alpha_0 + p_1[j] alpha_1 - sum_{1 <= i <= n} v_i[j] beta_i = 0
alpha_0 + alpha_1 = 1
sum_{1 <= i <= n} beta_i = 1

alpha_0 >= 0
alpha_1 >= 0
for 1 <= i <= n,
    beta_i >= 0

交点由点 p_0 alpha_0 + p_1 alpha_1 定义(除非程序不可行，在这种情况下没有交点)。