一連の頂点によって定義された凸形状があります。また、多数の点があり、凸形状に含まれている点をテストしたいと思います。現在、私はオープンソースの線形計画法ソルバーを各点に対して独立して一定の目的関数で使用しています。詳細については、 http: //www.stanford.edu/~boyd/cvxbook/bv_cvxbook.pdf の 11.4 章を参照してください。
ただし、これは 100 次元でもかなり遅いです。プロセスを高速化するために、すべてのクエリ ポイントが事前にわかっているという事実を利用する方法はありますか?
編集問題のタイプミスを修正しました。
私の提案は、形状内の点の凸包を見つけることです。これを LP ソルバーから直接取得する方法はすぐには思いつきませんが、その超平面の線形項を目的関数に追加することで、形状の特定の超平面に最も近い点を見つけることができます。シェイプのすべてのエッジに対してこれを繰り返し、各エッジに対してこれを数回繰り返します。そのたびに最新のソリューションを除外して、ますます遠くにある含まれるポイントを取得します。これにより、超平面に「近い」およびその内部にある多くの点が得られます。
船体ができたら、他のすべてのポイントを比較的迅速に船体の内側または外側に分類できるはずです。これをかなり迅速に行うアルゴリズムがあると確信していますが、私は何も知りません。多くの内部ポイントを取り除くことができる 1 つの潜在的に有用な方法は次のとおりです。空間が n 次元の場合、ハル上の n+1 ポイントを選択し、すべてのポイントをテストして、これらのポイントの凸結合であるかどうかを確認します (線形関数を使用)。代数）。