与えられた点を含む点のセットから最小のN次元のシンプレックスを見つけるには？

Question

Googleとスタックのすべてを見てきましたが、まだこの問題の答えが見つかりませんでした。私は、シンプレックス法に関する結果、または最小の任意のシンプレックス（すなわち、頂点は制約されていない）を見つけるための結果を探し続ける。どちらも、分析的な解決策を考えることはできません。

は Qを含有するN次元の点の集合、M、任意のN次元の点、Q、どのように私は最小のN次元シンプレックスを見つけるか、Sを考えますSの頂点がMである必要がある場合は、を内部ポイントとして使用しますか？私は最適化でそれを解決できると確信していますが、可能であれば分析的な解決策が必要です。決定論的なアルゴリズムもOKです。

することは私はもともとK最近傍アプローチを使用していたが、その後、私はそれがQにN + 1人の最も近い隣人は必ずしもQが含まれているシンプレックスを作成しないことがあります実現しました。

ご協力いただきありがとうございます。

Answer 1

私はあなたがK-NNと非常によく似た反復プロセスを使ってO（N^2）を行うことができると思いますが、おそらくもっと効率的な方法があります。これは、頂点の数に関して最小限のシンプレックスを返さなければなりません。各QでI座標について

、我々は、Q_IとM_Iを比較し、Mのすべての要素を反復処理することができます。 Mの2点を選択して、最小の正の差と最小の負の差を与えます。すべての座標についてこのプロセスを繰り返す場合は、最小値をSに設定する必要があります。

問題を正しく理解していますか？