船体自体を計算せずに点の集合の凸包の中に点があるかどうかを調べる

Question

点Pが点集合Xで形成された凸包の中にあるかどうかを調べる最も簡単な方法は？

凸包自体を明示的に計算しない高次元の空間（例えば、最大40次元）で動作するアルゴリズムが必要です。何か案は？

Answer 1

多次元空間では非常に面倒なので、凸包自体を計算する必要はありません。 well-known property of convex hullsがあります：

ポイント[v1, v2, .., vn]の凸包内部vはsum(ki*vi)、0 <= ki <= 1とsum(ki) = 1として提示することができる任意のベクター（ポイント）。これに対応して、凸包の外側にはそのような表現はありません。

m次元空間では、n未知数のmの線形方程式の集合が得られます。

編集
は、私は一般的なケースでは、この新しい問題の複雑さについてはよく分からないんだけど、m = 2のために、それは線形ようです。おそらく、この分野でより多くの経験を積んだ誰かが私を修正するでしょう。

Answer 2

通常は動作するはずですが保証されていないヒューリスティックな回答を受け入れますか？あなたがしている場合は、このランダムなアイデアを試すことができます。

X内のすべての点までの距離の立方体の合計を差し引いて、Xの物の数をP倍した距離の立方体をf（x）とし、丘を使用しますPから非常に遠い球内のxについてf（x）を最大にするようなクライミングアルゴリズムである。縮退の場合を除いて、Pが凸包にない場合、これは超平面の法線を見つける可能性が非常に高いはずである。の片側にあり、Xのすべてが反対側にあります。

Answer 3

ポイントは、それから他のポイントまでのすべてのベクトルの方向がその周りの円/球/超球の半分未満である場合に限り、他のポイントの凸包の外側にあります。

Answer 4

問題は、リニアプログラムの実行可能ポイントを見つけることで解決できます。既存のソルバーにLPを接続するのではなく、詳細を知りたい場合は、Boyd and Vandenberghe's excellent book on convex optimizationの第11.4章を読むことをお勧めします。

1. x^Tが転置である

   セット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

2. [1]はall-1ベクトルです。

問題は、ポイントが凸包にある場合、解決策があります。

Answer 5

私は16次元で同じ問題がありました。あまりにも多くの顔を生成しなければならないのでqhullでも正しく動作しなかったので、新しいポイントと参照データの間に分離超平面があるかどうかをテストすることで独自のアプローチを開発しました（私はこれを "HyperHull" 。

分離超平面を見つける問題は、凸2次計画問題（SVM参照）に変換することができます。私はPythonで、コード行数が170以下でcvxoptを使用していました（I/Oを含む）。このアルゴリズムは、問題が存在していても、どの次元でも変更することなく、船体上の点数が多くなるほど次元が大きくなる（On the convex hull of random points in a polytope参照）。船体は明示的に構成されておらず、チェックされているだけなので、点が内部にあるかどうかにかかわらず、アルゴリズムは、例えば、迅速な船体。

このアルゴリズムは「自然に」並列化することができ、スピードアップはプロセッサの数に等しくなければなりません。

Answer 6

元の投稿は3年前ですが、おそらくこの回答はまだ役立つでしょう。 Gilbert-Johnson-Keerthi（GJK）アルゴリズムは、2つの凸多面体の最短距離を求めます。各凸多面体は、複数の生成器の凸包として定義されます。凸包自体は計算する必要はありません。特別なケースでは、質問されている場合は、ポリトープの1つだけのポイントです。なぜGJKアルゴリズムを使ってPと点Xの凸包との距離を計算しようとしないのですか？その距離が0の場合、PはXの内側（または少なくともその境界上）にあります。サポートコードとともにClosestPointInConvexPolytopeGJK.mと呼ばれるOctave/MatlabでのGJKの実装は、http://www.99main.com/~centore/MunsellAndKubelkaMunkToolbox/MunsellAndKubelkaMunkToolbox.htmlで利用できます。 GJKアルゴリズムの簡単な説明はSect。 2の論文、http://www.99main.com/~centore/ColourSciencePapers/GJKinConstrainedLeastSquares.pdf。私は、31次元空間でいくつかの非常に小さな集合Xに対してGJKアルゴリズムを使用し、良好な結果を得ました。 GJKのパフォーマンスが、他の人が推薦している線形プログラミング方法とどのように比較されるかは不確かである（比較は興味深い）。 GJK法は、凸包を計算すること、または線形不等式の観点から船体を表現することを避けており、どちらも時間がかかることがあります。この回答が役立つことを願っています。