最小重み三角測量
全長を最小化する点集合三角測量
同じ多角形を三角形に分割できる3つの例。中央の三角形の重み（周囲の長さの合計）は小さくなります。

計算幾何学とコンピュータサイエンスにおいて、最小重み三角形分割問題は、総辺長が最小となる三角形分割を求める問題である。 [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] お （ n ） {\displaystyle O({\sqrt {n}})} 2 お （ n ログ ⁡ n ） {\displaystyle 2^{O({\sqrt {n}}\log n)}}

近似

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

MulzerとRoteの困難性の結果は、相対近似誤差が最大でもO(1/n 2 )である近似解を求めることのNP困難性も示唆している。したがって、最小重み三角測量のための完全な多項式近似スキームは考えにくい。しかし、準多項式近似スキームは可能である。任意の定数ε 0に対して、近似比1 + εの解は準多項式時間exp(O((log  n ) 9 )で求められる。[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]なども研究されている。

注記

  1. ^ この問題の調査については、Xu (1998)、Levcopoulos (2008)、および De Loera、Rambau & Santos (2010) を参照。
  2. ^ Manacher & Zobrist (1979)も参照。
  3. ^ リンガス（1998年）。
  4. ^ Kirkpatrick (1980)。より弱い上限はManacher & Zobrist (1979)によって示された。
  5. ^ 近似比が であることを証明する一連の例はLevcopoulos (1987)によって示されており、対応する上限はLevcopoulos & Krznaric (1998)によって示されています。Delaunay三角形分割の近似比と同様に、より弱い上限はManacher & Zobrist (1979)によっても示されています。 Ω （ n ） {\displaystyle \Omega ({\sqrt {n}})}
  6. ^ リンガス（1986年）。
  7. ^ Remy & Steger (2009). 多項式時間近似アルゴリズムに関する以前の結果については、Plaisted & Hong (1987) (対数係数近似) および Levcopoulos & Krznaric (1998) (定数係数近似) を参照してください。
  8. ^ チェン、ゴリン、ツァン (1995)。
  9. ^ リンガス (1987);ヒースとペマラジュ (1994)。
  10. ^ ヤン、シュウ、ユー (1994).
  11. ^ ケイル (1994);チェン、ゴリン、ツァン (1995); Cheng & Xu (2001);胡（2010）。
  12. ^ Dickerson & Montague (1996); Cheng, Katoh & Sugai (1996); Beirouti & Snoeyink (1998); Aichholzer, Aurenhammer & Hainz (1999).
  13. ^ Bose、Devroye、Evans（1996年）。
  14. ^ 秦、王、功 (1997);キャップとジュルストローム (1998)。
  15. ^ 京田ら（1997）。
  16. ^ ジャハニ、ビガム、アスカリ (2010).
  17. ^ ホフマン＆オカモト (2004);グラントソン、ボーゲルト、レフコプロス (2005)。クナウアーとスピルナー (2006)。
  18. ^ アナグノストウとコルニール (1993);マイヤーとラパポート (1992)。
  19. ^ エップスタイン（1994年）。
  20. ^ グズムンドソン＆レフコプロス (2007);アイヒホルツァーら。 （2009年）。
  21. ^ レンハート＆リオッタ（2002年）。

参考文献

  • Aichholzer, Oswin; Aurenhammer, Franz ; Hackl, Thomas; Speckmann, Bettina (2009)「最小重み擬似三角測量について」, Computational Geometry Theory and Applications , 42 ( 6– 7): 627– 631, doi : 10.1016/j.comgeo.2008.10.002 , MR  2519380。
  • Aichholzer, Oswin; Aurenhammer, Franz ; Hainz, Reinhard (1999)「MWTサブグラフに関する新たな結果」Information Processing Letters , 69 (5): 215– 219, doi :10.1016/S0020-0190(99)00018-6。
  • アナグノストウ, エフティミオス;コルネイユ, デレク(1993)、「最小重み三角測量問題の多項式時間例」、計算幾何学理論と応用、3 (5): 247– 259、doi : 10.1016/0925-7721(93)90016-Y、MR  1251594。
  • Beirouti, Ronald; Snoeyink, Jack (1998)、「最小重み三角測量におけるLMTヒューリスティックの実装」、Proc. 14th ACM Symposium on Computational Geometry、pp.  96– 105、doi : 10.1145/276884.276895、S2CID  15102126。
  • Bose, Prosenjit ; Devroye, Luc ; Evans, William (1996)「ダイヤモンドは最小重量三角形分割の最良の友ではない」第8回カナダ計算幾何学会議 (CCCG 1996) (PDF)、pp.  68– 73。
  • Capp, Kerry; Julstrom, Bryant A. (1998)、「最小重み三角測量問題のための重み符号化遺伝的アルゴリズム」、Proc. ACM Symposium on Applied Computing、アトランタ、ジョージア州、アメリカ合衆国、pp.  327– 331、doi :10.1145/330560.330833、S2CID  13589205、Semantic Sc​​holar{{citation}}: CS1 メンテナンス: 場所の発行元が見つかりません (リンク)。
  • Cheng, Siu-Wing; Golin, Mordecai; Tsang, J. (1995)、「 β-スケルトンの期待値解析と最小重み三角形分割の構築への応用」、Proc. 7th Canadian Conference on Computational Geometry (CCCG 1995)、pp.  279– 284。
  • Cheng, Siu-Wing; Katoh, Naoki; Sugai, Manabu (1996)、「LMTスケルトンの研究」、Algorithms and Computation、Lecture Notes in Computer Science、vol. 1178、pp.  256– 265、doi :10.1007/BFb0009502、ISBN 978-3-540-62048-8。
  • Cheng, Siu-Wing; Xu, Yin-Feng (2001)、「最小重み三角分割のサブグラフとしてのβスケルトンについて」、理論計算機科学、262 ( 1– 2): 459– 471、doi : 10.1016/S0304-3975(00)00318-2。
  • De Loera, Jesús A. ; Rambau, Jörg; Santos, Francisco (2010)、「3.2.3 貪欲法と最小重み三角分割」、Triangulations: Structures for Algorithms and Applications、Algorithms and Computation in Mathematics、第25巻、Springer、pp.  102– 107、ISBN 978-3-642-12970-4。
  • ディッカーソン, マシュー T. ; モンタギュー, マーク H. (1996)、「最小重み三角分割の（通常？）連結部分グラフ」、第12回ACM計算幾何学シンポジウム、pp.  204– 213、doi :10.1145/237218.237364、S2CID  18962760。
  • デュッペ、RD; Gottschalk、HJ (1970)、「Automatische Interpolation von Isolinien bei willkürlich verteilten Stützpunkten」、Allgemeine Vermessungs-Nachrichten、77 : 423–426Mulzer & Rote (2008)およびRemy & Steger (2009)による引用。
  • エップスタイン、デイヴィッド（1994）、「最小重みシュタイナー三角分割の近似」（PDF）、離散幾何学と計算幾何学、11（2）：163–191、doi：10.1007/BF02574002、MR  1254088。
  • ギャリー、MR ;ジョンソン、DS（1979）、コンピュータとイントラクタビリティ：NP完全性理論へのガイド、サンフランシスコ、カリフォルニア州：WHフリーマン、問題OPEN12、p。288、ISBN 0-7167-1045-5、MR  0519066。
  • ギルバート, PD (1979),平面三角測量における新しい結果, レポート R-850, イリノイ州アーバナ: イリノイ大学コーディネート科学研究所。
  • Grantson, M.; Borgelt, C.; Levcopoulos, C. (2005)「三角形の切り出しによる最小重み三角形分割」、第16回国際アルゴリズム・計算シンポジウム論文集、pp.  984– 994。
  • Gudmundsson, Joachim; Levcopoulos, Christos (2007)、「最小重み擬似三角測量」、計算幾何学理論と応用、38 (3): 139– 153、doi : 10.1016/j.comgeo.2007.05.004、MR  2352529。
  • Heath, LS; Pemmaraju, SV (1994)、「最小重み三角測量問題に関する新たな結果」、Algorithmica、12 (6): 533– 552、doi :10.1007/BF01188718、hdl : 10919/ 19701 、MR  1297812、S2CID  21160664。
  • ホフマン, M.; 岡本, Y. (2004)、「少数の内部点を持つ最小重み三角測量問題」、第1回パラメータ化および厳密計算に関する国際ワークショップ論文集、pp.  200– 212。
  • Hu, Shiyan (2010)、「最小重み三角測量のための新しい非対称包含領域」、Journal of Global Optimization、46 (1): 63– 73、CiteSeerX  10.1.1.377.6164、doi :10.1007/s10898-009-9409-z、MR  2566136、S2CID  869128。
  • Jahani, M.; Bigham, BS; Askari, A. (2010)「最小重み三角測量のためのアントコロニーアルゴリズム」、国際計算科学とその応用会議 (ICCSA)、pp.  81– 85、doi :10.1109/ICCSA.2010.38、S2CID  11790811、Semantic Sc​​holar。
  • Keil, J. Mark (1994)、「最小重み三角分割の部分グラフの計算」、計算幾何学：理論と応用、4 (1): 18– 26、doi : 10.1016/0925-7721(94)90014-0。
  • カークパトリック、デイビッド・G.（1980）「ドロネーと最適三角測量に関する注記」、情報処理レター、10（3）：127-128、doi：10.1016/0020-0190（80）90062-9、MR  0566856。
  • Klincsek, GT (1980)、「多角形領域の最小三角分割」、Annals of Discrete Mathematics、9 : 121– 123、doi :10.1016/s0167-5060(08)70044-x、ISBN 9780444861115。
  • Knauer, Christian; Spillner, Andreas (2006)、「小さなグラフセパレータに基づく最小重み三角測量問題のための固定パラメータアルゴリズム」、Graph-Theoretic Concepts in Computer Science、Lecture Notes in Computer Science、vol. 4271、ベルリン：Springer、pp.  49– 57、doi :10.1007/11917496_5、ISBN 978-3-540-48381-6、MR  2290717。
  • 京田 善明; 今井 恵子; 竹内 文彦; 田島 明 (1997)「最小重み三角測量のための分岐カット法」『アルゴリズムと計算』（シンガポール、1997年）『コンピュータサイエンス講義ノート』第1350巻、ベルリン：シュプリンガー、pp.  384– 393、doi :10.1007/3-540-63890-3_41、ISBN 978-3-540-63890-2、MR  1651067。
  • レンハート、ウィリアム；リオッタ、ジュゼッペ（2002）「最小重み三角形分割における描画可能性問題」、理論計算機科学、270（1-2）：261-286、doi：10.1016/S0304-3975（00）00383-2、MR  1871072。
  • レヴコプーロス、クリストス（1987）、「貪欲三角分割の非最適性に対するΩ（√n ）下限値」、情報処理レター、25（4）：247-251、doi：10.1016/0020-0190（87）90170-0、MR  0896144。
  • Levcopoulos, Christos (2008)、「最小重み三角測量」、Kao, Ming-Yang (編)、Encyclopedia of Algorithms、Springer、pp.  546– 548、ISBN 978-0-387-30770-1。
  • Levcopoulos, C.; Krznaric, D. (1998)、「最小重み三角形分割を近似する準貪欲三角形分割」(PDF)、Journal of Algorithms、27 (2): 303– 338、doi :10.1006/jagm.1997.0918、MR  1622398、S2CID  13991653。
  • リンガス、アンジェイ（1986）「貪欲法とドロネー法の三角形分割は平均的な場合には悪くない」、情報処理レター、22（1）：25-31、doi：10.1016/0020-0190（86）90038-4。
  • リンガス、アンジェイ（1987）、「最小重み三角測量のための新しいヒューリスティック」、SIAM Journal on Algebraic and Discrete Methods、8（4）：646–658、doi：10.1137/0608053、MR  0918066。
  • Lingas, Andrzej (1998)、「最小重み三角形分割および関連問題のための準指数時間アルゴリズム」、第10回カナダ計算幾何学会議 (CCCG'98) の議事録。
  • ロイド、E. (1977)、「平面上の点集合の三角測量について」、第18回IEEEコンピュータサイエンス基礎シンポジウム論文集、pp.  228– 240。
  • Manacher, Glenn K.; Zobrist, Albert L. (1979)、「平面点集合の貪欲法もドロネー法も最適な三角形分割を近似しない​​」、Information Processing Letters、9 (1): 31– 34、doi :10.1016/0020-0190(79)90104-2、MR  0537055。
  • マイヤー、ヘンク；ラパポート、デイビッド（1992）「線形順序付けされた点群の最小重み三角測量の計算」、情報処理レター、42（1）：35-38、doi：10.1016/0020-0190（92）90129-J、MR  1160443。
  • Mulzer, Wolfgang; Rote, Günter (2008)、「最小重み三角測量はNP困難である」、Journal of the ACM、55 (2)、Article A11、arXiv : cs.CG/0601002、doi : 10.1145 /1346330.1346336、S2CID  1658062。
  • プレイステッド、DA; Hon, J. (1987)、「ヒューリスティック三角測量アルゴリズム」、Journal of Algorithms、8 (3): 405–437、doi :10.1016/0196-6774(87)90020-4。
  • Qin, Kaihuai; Wang, Wenping; Gong, Minglun (1997)、「最小重み三角測量のための遺伝的アルゴリズム」、IEEE International Conference on Evolutionary Computation、pp.  541– 546、doi :10.1109/ICEC.1997.592370、hdl : 10722/45578、S2CID  18775737、Semantic Sc​​holar。
  • レミー、ヤン;ステガー、アンジェリカ(2009)、「最小重み三角測量のための準多項式時間近似法」、Journal of the ACM、56 (3)、Article A15、doi :10.1145/1516512.1516517、S2CID  1781658。
  • Shamos, MI ; Hoey, DJ (1975)、「最近接点問題」、第16回IEEEコンピュータサイエンス基礎シンポジウム論文集(PDF)、pp.  151– 162。
  • 王 曹安; 楊 棠婷 (2001)「最小重み三角形分割に属するβ-スケルトンの下限値」,計算幾何学：理論と応用, 19 (1): 35– 46, doi :10.1016/S0925-7721(01)00008-6。
  • Xu, Yin-Feng (1998)、「最小重み三角測量」、Handbook of Combinatorial Optimization、第2巻、ボストン、マサチューセッツ州：Kluwer Academic Publishers、pp.  617– 634、MR  1665412。
  • Yang, Bo Ting; Xu, Yin Feng; You, Zhao Yong (1994)、「最小重み三角形分割の特性の証明のための連鎖分解アルゴリズム」、Du, Ding-Zhu; Zhang, Xiang-Sun (編)、『アルゴリズムと計算：第5回国際シンポジウム、ISAAC '94』、北京、中国、1994年8月25～27日、議事録、Lecture Notes in Computer Science、第834巻、ベルリン：Springer、pp.  423～ 427、doi :10.1007/3-540-58325-4_207、ISBN 978-3-540-58325-7、MR  1316441。
  • LMTスケルトンソースコードを使用した最小重量三角測量
「https://en.wikipedia.org/w/index.php?title=Minimum-weight_triangulation&oldid=1323428697」より取得