最小重量三角測量

計算幾何学とコンピュータサイエンスにおいて、最小重み三角形分割問題は、合計辺の長さが最小となる三角形分割を求める問題である。^[1]つまり、入力ポリゴンまたは入力点集合の凸包を、三角形の周長の合計が最小となるように、辺同士および頂点同士が接する三角形に分割しなければならない。この問題は、点集合入力の場合NP困難だが、任意の精度に近似することができる。ポリゴン入力の場合、多項式時間で正確に解くことができる。最小重み三角形分割は、最適三角形分割と呼ばれることもある。

点集合の最小重み三角分割の問題は、Düppe & Gottschalk (1970) によって提起され、彼らはそれを土地の等高線の三角形の不規則ネットワークモデルの構築に応用することを提案し、貪欲なヒューリスティックを使用して近似しました。Shamos & Hoey (1975) は、最小重み三角分割は常にDelaunay 三角分割と一致すると推測しましたが、これは Lloyd (1977) によってすぐに反証され、実際、Kirkpatrick (1980) は 2 つの三角分割の重みが線形係数で異なる可能性があることを示しました。^[2]

最小重量三角分割問題は、Garey と Johnson (1979) がNP 完全性に関する著書の中でこの問題を未解決問題のリストに含めたことで悪名高くなり、その後多くの著者がこの問題の部分的な結果を発表しました。最終的に、Mulzer と Rote (2008) はこれが NP 困難であることを示し、Remy と Steger (2009) は、この問題の正確な近似を効率的に構築できることを示しました。

ユークリッド平面上の点の集合の三角形分割の重みは、その辺の長さの合計として定義されます。その決定変種は、与えられた重みより小さい重みの三角形分割が存在するかどうかを判断する問題です。これは、 Mulzer と Rote (2008) によってNP 困難であることが証明されました。彼らの証明は、ブール充足可能性問題の特殊なケースである PLANAR-1-IN-3-SAT からの還元によるもので、ブール充足可能性問題では、グラフが平面である3-CNF は、各節で正確に 1 つのリテラルを満たす真理値割り当てを持つ場合に受け入れられます。証明では複雑なガジェットが使用され、これらのガジェットの正しい動作を検証するために コンピューターの支援が必要です。

最小重みの三角形分割決定問題がNP 完全であるかどうかは不明です。これは、根号の和が多項式時間で計算できるかどうかという既知の未解決問題に依存するためです。ただし、Mulzer と Rote は、エッジの重みが整数値に丸められる場合、問題は NP 完全であると述べています。

NP困難ではあるが、最小重みの三角形分割は、三角形分割内の点の可能なすべての単純なサイクルセパレータを考慮し、サイクルの各側で最適な三角形分割を再帰的に見つけ、合計重みが最小になるサイクルセパレータを選択する動的計画法アルゴリズムによって、準指数時間で構築できる。この方法の合計時間は である。^[3]${\displaystyle O({\sqrt {n}})}$${\displaystyle 2^{O({\sqrt {n}}\log n)}}$

複数の著者が、近似比 （代替三角形分割の合計辺長と最小重み三角形分割の合計辺長の最悪比）の観点から、最小重み三角形分割と他の三角形分割との関連を証明しています。この意味で、ドロネー三角形分割の近似比は、^[4]であり、貪欲三角形分割（各ステップで前の辺と交差しない辺を含め、最短から最長の順に辺を追加することによって形成される三角形分割）の近似比は であることが知られています。^[5]ただし、ランダムに分布した点集合の場合、ドロネー三角形分割と貪欲三角形分割の両方が最小重みの対数係数の範囲内にあります。^[6]${\displaystyle \Theta (n)}$${\displaystyle \Theta ({\sqrt {n}})}$

MulzerとRoteの困難性の結果は、相対近似誤差が最大でもO(1/n ² )の近似解を見つけることがNP困難であることをも意味している。したがって、最小重み三角測量のための完全な多項式近似スキームはありそうにない。しかし、準多項式近似スキームは可能であり、任意の定数ε 0に対して、近似比1 + εの解は準多項式時間exp(O((log  n ) ⁹ )で見つけることができる。^[7]

最小重み三角形分割の正確な解を見つけるのは難しいため、多くの著者が、すべての場合に機能するとは証明できないものの、場合によっては解を見つけることができるヒューリスティックを研究してきました。特に、この研究の多くは、最小重み三角形分割に属することが保証されているエッジのセットを見つける問題に焦点を当てています。このようにして見つかった最小重み三角形分割のサブグラフが接続されていることが判明した場合、残りの三角形分割されていない空間は単純な多角形を形成していると見なすことができ、動的計画法を使用してこの多角形空間の最適な三角形分割を見つけることで、三角形分割全体を見つけることができます。同じ動的計画法のアプローチは、サブグラフが接続されたコンポーネントの数に制限がある場合にも拡張できます^[8]。また、接続されたグラフを見つけてから動的計画法を適用してグラフのエッジを囲む多角形のギャップを埋める同じアプローチは、最小重みではなく低重みの三角形分割を見つけるためのヒューリスティックの一部としても使用されています。^[9]

2 つの点が互いに最近接である場合に接続して形成されるグラフは、必然的に最小重み三角形分割のサブグラフになります。^[10]ただし、この相互最近接グラフはマッチングであるため、接続されることはありません。関連する研究では、円ベースのβスケルトン を使用して、最小重み三角形分割の大きなサブグラフを見つけます。βスケルトンとは、あるパラメーター θ より大きい角度uwv を形成する 3 番目の点wが存在しない場合に、 2 つの点uとvの間にエッジを含めることによって形成される幾何学的グラフです。θ の値が十分に小さい場合、このようにして形成されたグラフは、最小重み三角形分割のサブグラフであることが示されています。^[11]ただし、これを保証するために必要な θ の選択は、βスケルトンが常に接続される角度{{{1}}}よりも小さくする必要があります。

Dickerson と Montague (1996) は、より洗練された手法である LMT スケルトンを提案しました。これは反復プロセスによって形成され、最小重み三角形分割に属することがわかっているエッジのセットと、それに属する候補となるエッジのセットの 2 つのエッジ セットが維持されます。最初に、既知のエッジ セットが入力の凸包に初期化され、残りのすべての頂点のペアが候補エッジを形成します。次に、構築プロセスの各反復で、残りのエッジによって形成される三角形のペアがなく、候補エッジが最短の対角線である四辺形がない場合は常に候補エッジが削除され、交差する他の候補エッジがない場合には候補エッジが既知のエッジ セットに移動されます。LMT スケルトンは、このプロセスがそれ以上の変更を行わなくなった後に生成される既知のエッジ セットとして定義されます。これは最小重み三角分割のサブグラフであることが保証されており、効率的に構築でき、最大200点の集合での実験では頻繁に連結されていました。^[12]しかし、平均すると大きな点集合では連結成分の数が線形であることが示されています。^[13]

最小重量三角測量問題に適用されている他のヒューリスティックスとしては、遺伝的アルゴリズム^[14]、 分岐限定法^[15]、蟻コロニー最適化アルゴリズム^[16]などがある。

最小の重みを持つ多角形の三角形分割は、Gilbert (1979) と Klincsek (1980) がそれぞれ独立に報告した動的計画法のアプローチを使用して、3 次時間で構築できます。この方法では、頂点は多角形の境界の周囲で連続的に番号が付けられ、多角形内にある頂点 i から頂点 j までの各対角線について、多角形内のすべての可能な三角形 ijk を考慮し、対角線ikとjkの下の最適な三角形分割の重みを追加し、合計の重みが最小になる頂点k を選択することで、最適な三角形分割が計算されます。つまり、MWT( i , j ) が辺ijの下の多角形の最小重み三角形分割の重みを表す場合、全体的なアルゴリズムは次の手順を実行します。

• n − 1から 1 までの 各iの可能な値に対して、次の操作を実行します。
  • i  + 1からnまでのjの可能な値ごとに、次の操作を実行します。
    • ijがポリゴンの辺である場合、MWT( i , j ) = length( ij )と設定する。
    • それ以外の場合、ijが多角形の内対角線でない場合は、MWT( i , j ) = +∞と設定する。
    • それ以外の場合は、 MWT( i , j ) = length( ij ) + min _{i < k < j} MWT( i , k ) + MWT( k,j )を設定します。

この反復処理が完了すると、MWT(1, n ) には最小重みの三角測量の合計重みが格納されます。三角測量自体は、MWT(1, n ) から始めてこの配列を再帰的に検索し、各ステップで MWT( i , j )の最小値をもたらす三角形ijkを選択し、MWT( i , k ) と MWT( j , k ) を再帰的に検索することで取得できます。

同様の動的計画法は、定数個を除くすべての点が入力の凸包上にある点集合入力にも適用できる。 ^[17]また、定数個の入れ子になった凸多角形上または凸包内で2つが交差しない定数個の線上に存在する点集合にも適用できる。^[18]

点集合または多角形三角形分割問題のバージョンを定式化することもできます。このバージョンでは、シュタイナー点、つまり追加の頂点を追加して、結果として得られる三角形分割の合計辺の長さを短縮できます。場合によっては、結果として得られる三角形分割は、最小重み三角形分割よりも線形係数だけ短くなることがあります。点集合の最小重みシュタイナー三角形分割を最適値の定数係数以内に近似することは可能ですが、近似の定数係数は大きくなります。^[19]

関連する問題としては、最小重み擬似三角形分割の構築^[20]や最小重み三角形分割のグラフの特徴付け^{[21]なども研究されている。}

• LMT スケルトン ソース コードを使用した最小重量三角測量