查找点是否在一组点的凸包内，而无需计算凸包本身

问题描述

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

What is the simplest way to test if a point P is inside a convex hull formed by a set of points X?

我想要一种在高维空间(例如，最多 40 维)中工作的算法，它不会显式计算凸包本身.有什么想法吗?

I'd like an algorithm that works in a high-dimensional space (say, up to 40 dimensions) that doesn't explicitly compute the convex hull itself. Any ideas?

推荐答案

该问题可以通过找到线性规划的可行点来解决.如果您对完整细节感兴趣，而不是仅仅将 LP 插入现有求解器，我建议您阅读 Boyd 和 Vandenberghe 关于凸优化的优秀著作.

The problem can be solved by finding a feasible point of a Linear Program. If you're interested in the full details, as opposed to just plugging an LP into an existing solver, I'd recommend reading Chapter 11.4 in Boyd and Vandenberghe's excellent book on convex optimization.

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

Set A = (X[1] X[2] ... X[n]), that is, the first column is v1, the second v2, etc.

解决下面的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 向量.

1. x^T is the transpose of x
2. [1] is the all-1 vector.

当点在凸包中时，问题有解.

The problem has a solution iff the point is in the convex hull.

这篇关于查找点是否在一组点的凸包内，而无需计算凸包本身的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！