在不计算船体本身的情况下,查找一个点是否在一组凸包内部
dim*_*imi 42 algorithm graphics geometry computational-geometry
测试点P是否在由一组点X形成的凸包内的最简单方法是什么？
我想要一种在高维空间(例如,最多40维)中工作的算法,该算法不会明确地计算凸包本身.有任何想法吗？
use*_*136 23
通过找到线性程序的可行点可以解决该问题.如果您对完整的细节感兴趣,而不是将LP插入现有的求解器,我建议您阅读Boyd和Vandenberghe关于凸优化的优秀书中的第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矢量.
如果该点位于凸包中,则问题有解决方案.
Sva*_*nte 21
该点位于其他点的凸包之外,当且仅当所有矢量从其到其他点的方向不到其周围的圆/球/超球的一半时.
这是两个点情况的草图,凸面船体内部的蓝色部分(绿色)和外部的红色部分:
对于红色的那个,存在圆的二等分,使得从点到凸包上的点的矢量仅与圆的一半相交.对于蓝点,不可能找到这样的二分法.
- 这是不够的,埃文斯.但是你可以这样做:将所有向量从点到其他点相加.然后,使用该求和的矢量作为轴再次投影来自所讨论的点的所有矢量.如果所有投影位于轴的同一侧,则该点位于船体外部.我认为这是O(m*n) (2认同)
Nik*_*bak 10
您不必计算凸包本身,因为它在多维空间中看起来相当麻烦.有一个众所周知的凸壳属性:
点v凸壳内的任何矢量(点)[v1, v2, .., vn]可以表示为sum(ki*vi),where 0 <= ki <= 1和sum(ki) = 1.相应地,凸包外的任何点都不具有这种表示.
在m维空间中,这将给出一m组具有n未知数的线性方程.
编辑
我不确定这个新问题的复杂性在一般情况下,但因为m = 2它似乎是线性的.也许,在这方面有更多经验的人会纠正我.
- 实际上在m维空间中你只需要m + 1分,因为Carathéodory定理:http://en.wikipedia.org/wiki/Carathéodory's_theorem_(convex_hull)困难是找到m + 1分的工作. (4认同)
- 问题在于线性代数很容易为你提供解决方程式的nm维空间,但是没有给你任何简单的方法来满足不等式.因此,你引用的定理是一个很好的方法来表明一个点在m + 1点的凸包内,但是对于一个更大的点集,你需要找到正确的m + 1点集来利用所述定理.有n个选择m + 1这样的套装试试.在40个维度中,这将是一个问题. (3认同)