测试点 P 是否在由一组点 X 形成的凸包内的最简单方法是什么?
我想要一种在高维空间(例如,最多 40 维)中运行且不会显式计算凸包本身的算法。有什么想法吗?
最佳答案
问题可以通过找到线性规划的可行点来解决。如果您对全部细节感兴趣,而不是仅仅将 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
在哪里
x^T
是x
的转置
[1]
是全 1 向量。
当且仅当该点在凸包中时,问题有解。
关于algorithm - 在不计算凸包本身的情况下查找点是否在一组点的凸包内,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/4901959/