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

问题描述

这是测试一个点P是由一组点的X形成的凸包内的最简单的方法是什么？我想，不明确地计算的凸壳本身的算法在高维空间的工作（例如，多达40个尺寸）。任何想法？

What is the simplest way to test if a point P is inside a convex hull formed by a set of points X? 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到现有的解算器，我建议你阅读本章11.4的 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.

解决以下线性规划问题，

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屋！