2つのポリラインの間に最小限の面積を持つメッシュ

Question

2つのポリラインvとuとnとmの頂点がそれぞれ3Dにあります。 v[0]をu[0]に、v[n-1]をu[m-1]に接続し、内側の頂点をどういうわけか最小限の表面積を持つ三角形のメッシュストリップにする必要があります。

私のナイーブな解決策は、最小の対角線を後で追加することによって最適に近い初期メッシュを取得し、それがもはや不可能になるまでより小さい面積を生成するならば、四角形ごとに対角線を切り替えることです。

しかし、私はグローバル極小値で終了とすることはできません怖いです。最小限のメッシュを達成するためのより良い選択肢は何ですか？

Answer 1

これは、動的プログラムで解決できます。

だが、列が最初のポリラインの頂点を表し、行は第二のポリラインの頂点を表すテーブル、等の問題を可視化してみましょう：

0 1 2 3 ... n-1 -> v 
0 
1 
2 
... 
m-1 

すべてのセルがポリライン間のエッジを表しています。 (0, 0)で始まり、(+1, 0)または(0, +1)ステップのいずれかを取って(n-1, m-1)へのパスを探したいとします。あなたが作るすべてのステップにはコスト（結果として生じる三角形の面積）があり、最小コストをもたらすパスを見つけたいと思っています。

したがって、（ダイナミックプログラミングのスタイルで）セルに到達するために必要なコストを計算することができます（2つの可能な到着方向の結果コストを比較することによって）。あなたが選んだ方向を覚えていれば、最後には最小コストの完全な道があります。ランタイム全体はO(n * m)になります。

頂点が多かれ少なかれ分散していることがわかっている場合は、テーブルの計算を対角線の近くのいくつかのエントリに制限することができます。これにより、ランタイムがO(k * max(n, m))になる可能性があります。kは対角線の周りの可変半径です。しかし、良い頂点分布の仮定が成り立たなければ、最適解を見逃してしまうかもしれません。

セルを最小パスに属すると思ったときにのみ計算する、A *のような戦略を採用することもできます（ヒューリスティックの助けを借りて）。