Loading article…
交差点 1 件
交差点2か所
交差点3か所以上
上の 2 つの多角形はLに関して単調ですが、下の 2 つはそうではありません。幾何学において、平面上の多角形 P が直線Lに関して単調であるとは、Lに直交するすべての線分がPの境界と最大で2回交差する場合をいう。[1]
同様に、多角形連鎖 Cが直線Lに関して単調であるとは、 Lに直交するすべての線分がC と最大で 1 回交差する場合を言います。
多くの実用的な目的のために、この定義は、 Pのいくつかの辺がLに直交するケースを許容するように拡張することができ、P内の 2 つの点を結び、Lに直交する線分が完全にP内にある場合、単純な多角形は単調であると言える。
単調関数の用語に従って、前者の定義はLに関して厳密に単調な多角形を記述します。
プロパティ
L がx軸と一致すると仮定します。すると、単調多角形の左端と右端の頂点は、その境界を 2 つの単調多角形チェーンに分解します。チェーンの頂点を自然な順序でたどると、その X 座標は単調に増加または減少します。実際、この特性は単調多角形の定義としてとらえられ、多角形の名前の由来となっています。
凸多角形は任意の直線に対して単調であり、すべての直線に対して単調である多角形は凸です。
線形時間アルゴリズムは、与えられた単純な多角形が単調であるすべての方向を報告することが知られています。[2]これは、単純な多角形を2つの単調なチェーン（異なる方向で単調である可能性もあります）に分解するすべての方法を報告するように一般化されました。[3]
単調な多角形に関する多角形内の点のクエリは、線形時間の前処理（左端と右端の頂点を見つける）の後、対数時間で回答される場合があります。 [1]
単調な多角形は線形時間で簡単に三角形に分割できる。 [4]
平面上の点の集合が与えられた場合、ビトニックツアーは点を結ぶ単調な多角形です。固定方向に対する点集合の最小周囲ビトニックツアーは、動的計画法を使用して多項式時間で見つけることができます。[5]このような最小ビトニックツアーが単純な多角形であることは簡単に示されます。つまり、交差するエッジのペアは、新しいツアーのビトニック性を維持しながら、より短い非交差エッジのペアに置き換えることができます。
単純な多角形は、 O ( n log n ) 時間で 簡単に単調な多角形に分割できます。ただし、三角形は単調な多角形であるため、多角形の三角分割は実際には多角形を単調な多角形に分割することであり、複雑なアルゴリズムを使用して単純な多角形に対してO ( n ) 時間で実行できます。 [6]線形期待時間を持つより単純なランダム化アルゴリズムも知られています。[7]
単純な多角形を最小数の均一な単調な多角形（すなわち、同じ線に関して単調な多角形）に分割することは、多項式時間で実行できます。[8]
動作計画の文脈では、交差しない2つの単調な多角形は1回の並進によって分離可能であり（つまり、1つの多角形を並進させると、2つの多角形が直線で異なる半平面に分離される）、この分離は線形時間で検出される可能性がある。[9]
一般化
スイープ可能なポリゴン
多角形は、直線が多角形全体にわたって連続的に移動でき、その多角形領域との交点が常に凸集合になる場合、スイープ可能と呼ばれます。単調な多角形は、スイープ中に方向が変化しない線によってスイープ可能です。多角形のどの部分も複数回スイープされない場合、多角形は厳密にスイープ可能です。両方のタイプのスイープ可能性は、2次時間で認識されます。 [10]
3D
多角形の単調性を高次元に単純に一般化したものはありません。
一つのアプローチでは、保存された単調性特性は直線Lである。3次元多面体は、Lに直交するすべての断面が単純な多角形である場合、方向Lで弱単調であると呼ばれる。断面が凸である場合、多面体は凸の意味で弱単調であると呼ばれる。[9]どちらのタイプも多項式時間で認識できる。[10]
別のアプローチでは、保存される 1 次元の特性は直交方向です。これにより、 3 次元の多面体地形の概念が生まれます。これは、各垂直線 (つまり、Z 軸に平行な線) が最大 1 つの点またはセグメントで表面と交差するという特性を持つ多面体表面です。
参照
参考文献
- ^ ab Preparata, Franco P. ; Shamos, Michael Ian (1985)、計算幾何学入門、Springer-Verlag、ISBN 0-387-96131-3、第 1 版、第 2 刷、修正および増補、1988 年:; ロシア語訳、1989 年
- ^ Preparata, Franco P. ; Supowit, Kenneth J. (1981)、「単純な多角形の単調性のテスト」、Information Processing Letters、12 (4): 161–164、doi :10.1016/0020-0190(81)90091-0。
- ^ ラパポート、デイビッド、ローゼンブルーム、アーノルド（1994）、「成形可能および鋳造可能な多角形」、計算幾何学、4（4）：219–233、doi：10.1016 / 0925-7721（94）90020-5。
- ^ Fournier, A. ; Montuno, DY (1984)、「単純な多角形の三角分割と同等の問題」、ACM Transactions on Graphics、3 (2): 153–174、doi : 10.1145/357337.357341、ISSN 0730-0301、S2CID 33344266
- ^ Introduction to Algorithms、第 2 版、TH Cormen、CE Leiserson、R. Rivest、およびC. Stein、MIT Press、2001。問題 15-1、p. 2001。 364.
- ^ シャゼル、バーナード（1991）、「線形時間での単純多角形の三角測量」、離散および計算幾何学、6（3）：485–524、doi：10.1007 / BF02574703、ISSN 0179-5376
- ^ アマト、ナンシー M. ;グッドリッチ、マイケル T. ; ラモス、エドガー A. (2001)、「単純な多角形を線形時間で三角分割するためのランダム化アルゴリズム」、離散および計算幾何学、26 (2): 245–265、doi : 10.1007/s00454-001-0027-x、ISSN 0179-5376
- ^ Liu, Robin (1988)、「多角形を均一な単調な部分に分解することについて」、Information Processing Letters、27 (2): 85–89、doi :10.1016/0020-0190(88)90097-X。
- ^ ab Toussaint, GT ; El Gindy, HA (1984)、「線形時間での2つの単調多角形の分離」、Robotica、2 (4): 215–220、doi :10.1017/S0263574700008924、S2CID 21790511。
- ^ ab Bose, Prosenjit ; van Kreveld, Marc (2005)、「単調性の一般化: ナイススイープの計算による多角形と多面体の特殊クラスの認識について」、International Journal of Computational Geometry & Applications、15 (6): 591–608、doi :10.1142/S0218195905001877、hdl : 1874/24150。