algorithm - 在不计算凸包本身的情况下查找点是否在一组点的凸包内

Question

测试点 P 是否在由一组点 X 形成的凸包内的最简单方法是什么？

我想要一种在高维空间(例如，最多 40 维)中运行且不会显式计算凸包本身的算法。有什么想法吗？

Answer 1

问题可以通过找到线性规划的可行点来解决。如果您对全部细节感兴趣，而不是仅仅将 LP 插入现有求解器，我建议您阅读 Boyd and Vandenberghe's excellent book on convex optimization 中的第 11.4 章。 .

设A = (X[1] X[2] ... X[n])，即第一列为v1，第二列v2等

解决以下LP问题，

minimize (over x): 1
s.t.     Ax = P
         x^T * [1] = 1
         x[i] >= 0  \forall i

在哪里

1. x^T 是 x
的转置
2. [1] 是全 1 向量。

当且仅当该点在凸包中时，问题有解。