查找一个点是否在一组点的凸包内而不计算包本身 [英] Find if a point is inside a convex hull for a set of points without computing the hull itself

问题描述

测试点 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 问题，

Solve the following LP problem,

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.

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