単純多角形

幾何学において、単純多角形とは、自身と交わらず、かつ穴のない多角形のことである。つまり、有限個の線分からなる区分的線形ジョルダン曲線である。これらの多角形には、凸多角形、星形多角形、単調多角形といった特殊な場合が含まれる。

単純多角形の外角の合計は$2π$。すべての単純な多角形は${\displaystyle n}$辺は三角形に分割できます${\displaystyle n-3}$その対角線によって、また美術館の定理によりその内部はいくつかの場所から見ることができる。${\displaystyle \lfloor n/3\rfloor }$その頂点の。

単純多角形は、点と多角形の内接判定、面積計算、単純多角形の凸包、三角形分割、ユークリッド最短経路など、計算幾何学の問題への入力としてよく用いられます。

単純多角形に関連する幾何学におけるその他の構成には、単純多角形を含む等角写像を見つけるために使用されるシュワルツ・クリストッフェル写像、点集合の多角形化、多角形の構成的立体幾何学公式、および多角形の可視性グラフなどがある。

単純多角形は、ユークリッド平面上の閉じた曲線で、直線の線分が端と端でつながって多角形の連鎖を形成します。[ 1 ^{] 2つ}の線分はすべての端点で交わり、線分間に他の交点はありません。線分の真部分集合はどれも同じ性質を持ちません。 ^{[ 2 ]}「単純」という修飾語は省略されることがあり、その場合は「多角形」という言葉は単純多角形を意味するものとみなされます。^{[ 3 ]}

多角形を形成する線分は、辺または側面と呼ばれます。線分の端点は、頂点（複数形：頂点）^{[ 2 ]}または角と呼ばれます。辺と頂点はより正式な用語ですが、グラフの辺と頂点も含まれる文脈では曖昧になる場合があります。この曖昧さを避けるために、より口語的な側面と角を使用できます。^{[ 4 ]}辺の数は常に頂点の数に等しくなります。^{[ 2 ]}一部の資料では、2 つの線分が直線角(180°) を形成することを許可していますが、^{[ 5 ]}他の資料ではこれを許可せず、閉じた多角形の連鎖の共線セグメントを 1 つのより長い辺に結合することを要求しています。^{[ 6 ]} 2 つの頂点は、多角形のいずれかの辺の 2 つの端点である場合、隣接しています。 ^{[ 7 ]}

単純多角形は、ジョルダン曲線であることから、ジョルダン多角形と呼ばれることがあります。ジョルダン曲線の定理を用いると、このような多角形が平面を 2 つの領域に分割することが証明できます。^{[ 8 ]}実際、カミーユ・ジョルダンによるこの定理の元の証明は、単純多角形（証明なしで述べられている）の特殊な場合を出発点としていました。^{[ 9 ]}多角形の内側の領域（内部）は、ジョルダン・シェーンフリースの定理により、位相的に開円盤と等価な有界集合を形成します^{。[2] 面積は有限ですがゼロではありません。[} 10 ]多角形自体は位相^的に円と^等価であり^、外側の領域（外部）は、面積が無限である非有界^連結開集合です。^{[ 12 ] [ 11 ]}単純多角形の正式な定義は通常、線分のシステムとして定義されますが、平面上の閉じた集合、つまりこれらの線分と多角形の内部との和集合として単純多角形を定義することも可能であり、非公式な使用法では一般的です。^{[ 2 ]}

単純多角形の対角線とは、2つの多角形の頂点を端点とし、それ以外は完全に多角形の内部にある線分のことである。^{[ 13 ]}

単純多角形の頂点の内角は、その頂点における多角形の内部が作る角度です。頂点の内角が1/2より小さい場合、その頂点は凸です。${\displaystyle \pi }$（直線、180°）内角が180°より大きい場合は凹角となる。${\displaystyle \pi }$内角が${\displaystyle \theta }$同じ頂点における外角は、その補角として定義される。${\displaystyle \pi -\theta }$、ある方向の側から次の方向の側への回転角。外角は凸頂点では正、凹頂点では負になります。すべての単純多角形において、外角の合計は$2π$（1回転、360°）。したがって、単純な多角形の内角の合計は、${\displaystyle n}$側面は${\displaystyle (n-2)\pi }$[ ^{14 ]​}

すべての単純多角形は、その対角線の部分集合によって重なり合わない三角形に分割できます。多角形が${\displaystyle n}$側面では、これにより${\displaystyle n-2}$三角形は、${\displaystyle n-3}$対角線。結果として得られる分割は多角形の三角形分割と呼ばれます。^{[ 8 ]}三角形分割された単純多角形の形状は、多角形の内角と、対角線を共有する三角形のペアによって形成される四角形の交差比によって一意に決定できます。^{[ 15 ]}

2つの耳の定理によれば、三角形ではないすべての単純多角形には、少なくとも2つの耳、つまり2つの隣接頂点が対角線の端点である頂点が存在する。^{[ 8 ]}関連する定理によれば、凸多角形ではないすべての単純多角形には、口、つまり2つの隣接頂点が、それ以外は多角形の外側にある線分の端点である頂点が存在する。ちょうど2つの耳と1つの口を持つ多角形は、人型多角形と呼ばれる。^{[ 16 ]}

美術館の定理によれば、${\displaystyle n}$頂点の場合、最大で の部分集合を見つけることは常に可能です${\displaystyle \lfloor n/3\rfloor }$多角形内のすべての点が選択された頂点のいずれかから見えるという性質を持つ頂点。これは、各点について、${\displaystyle p}$多角形内には、線分が接続されています。${\displaystyle p}$選択された頂点まで、多角形の内部点のみを通過する。これを証明する一つの方法は、多角形の三角形分割にグラフ彩色を用いることである。頂点を常に3色で彩色することが可能であり、三角形分割の各辺または対角線には、異なる色の2つの端点が存在する。多角形の各点は、各色の頂点から見える。例えば、選択された三角形分割においてその点を含む三角形の3つの頂点のうちの1つである。1つの色は、最大で${\displaystyle \lfloor n/3\rfloor }$頂点の定理を証明する。^{[ 17 ]}

すべての凸多角形は単純多角形です。単純多角形のもう1つの重要なクラスは星形多角形です。星形多角形とは、すべての点が見える点（内部または境界上）を持つ多角形のことです。^{[ 2 ]}

直線に関して単調多角形${\displaystyle L}$は、 に垂直なすべての線が であるような多角形です。${\displaystyle L}$多角形の内部と連結した集合で交差する。言い換えれば、境界が 2 つの単調多角形チェーン、つまり頂点を垂直に投影したときに 2 つの単調多角形チェーン、つまり辺のサブシーケンスに分割できる多角形である。${\displaystyle L}$同じ順序で${\displaystyle L}$連鎖反応で起こるように。^{[ 18 ]}

計算幾何学において、いくつかの重要な計算タスクでは、単純な多角形の形で入力が用いられる。

• 多角形の点のテストでは、単純な多角形の場合、${\displaystyle P}$そしてクエリポイント${\displaystyle q}$、 かどうか${\displaystyle q}$内部に位置する${\displaystyle P}$線形時間で解決できます。あるいは、与えられた多角形を線形時間でデータ構造に処理し、その後の多角形内の点のテストを対数時間で実行することも可能です。^{[ 20 ]}
• 多角形の内部の面積を計算するための簡単な公式が知られています。これらには、任意の多角形に対する靴ひも公式^{[ 21 ]}や、頂点座標が整数の多角形に対するピックの定理^{[ 12 ] [ 22 ]などがあります。}
• 単純多角形の凸包も線形時間で求めることができ、多角形に接続されていない点の凸包を求めるアルゴリズムよりも高速である。 ^{[ 6 ]}
• 単純多角形の三角形分割も、アルゴリズムは複雑ではあるものの、線形時間で実行できる。同じアルゴリズムの修正版は、閉じた多角形の連鎖が単純多角形を形成しているかどうか（つまり、自己交差を回避しているかどうか）を線形時間でテストするためにも使用できる。^{[ 23 ]}これにより、最大でも 100 の計算量で美術館問題を解くための線形時間アルゴリズムも得られる。${\displaystyle \lfloor n/3\rfloor }$点を使用するが、必ずしも与え​​られた多角形に対して最適な点の数を使用するわけではない。^{[ 24 ]}同じ多角形の任意の2つの三角形分割を、一度に1つの対角線を置き換える反転によって相互に変換することは可能であるが、限られた数の反転のみを使用してこれを行うことができるかどうかを判断することはNP完全である。^{[ 25 ]}
• 測地線経路^{[ 26 ]、}すなわち多角形の内部にある2点を外部に出ることなく結ぶ平面上の最短経路は、三角測量をサブルーチンとして使用するアルゴリズムによって線形時間で見つけることができます。[ 27 ^]測地線中心についても同様で、これは多角形内の点であり、他のすべての点への測地線経路の最大長を最小化します。^{[ 26 ]}
• 単純多角形の内部点の可視多角形、つまり多角形の内部の線分によって与えられた点から直接見える点の集合は、線形時間で構築できます。^{[ 28 ]}与えられた線分の少なくとも1つの点から見える部分集合についても同様です。^{[ 27 ]}

単純多角形について研究されたその他の計算問題には、多角形の内部にある最長の対角線または最長の線分の構築^{[ 13 ]} 、凸頭蓋（与えられた単純多角形内の最大の凸多角形）の構築^{[ 29 ] [ 30 ]} 、および中軸^{[ 31 ]}や直線骨格[32]を含む、その形状を近似するさまざまな一次元骨格の構築が含まれます。研究者はまた、オフセット曲線^{[ 33 ]}、和集合と交差[11]、^{ミンコフスキー和[} 34 ]を^{使用して単純多角形から他の多角形を生成することを研究しましたが、これらの操作は必ずしも結果として単純多角形を生成するとは限りません。これらは常に二次元領域を生成するように定義できますが、一次元}の特徴や孤立点の作成を避けるために、交差と差分操作を注意深く定義する必要があります。^{[ 11 ]}

リーマン写像定理によれば、平面の任意の単連結開集合は円盤に等角写像できる。シュワルツ・クリストッフェル写像は、指定された頂点角と円盤の境界上の多角形の頂点の逆像を用いて、円盤から任意の単純多角形への写像を明示的に構築する方法を提供する。これらの逆頂点は通常、数値的に計算される。^{[ 35 ]}

平面上の任意の有限個の点の集合は、単一の直線上にない限り、単純な多角形の頂点を形成するように接続できます（180°の角度を許容します）。たとえば、そのような多角形の1つは、巡回セールスマン問題の解です。^{[ 36 ]}このように点を接続して多角形を形成することを多角形化と呼びます。^{[ 37 ]}

すべての単純多角形は、半平面の和集合と交差から多角形（内部を含む閉集合として）を構成する式で表すことができ、多角形の各辺は式の中で半平面として一度だけ現れます。${\displaystyle n}$この表現への 辺多角形の変換は時間で実行できます${\displaystyle O(n\log n)}$[ ^{38 ]​}

単純多角形の可視グラフは、多角形の辺と対角線を表す辺で頂点を結びます。^{[ 3 ]}常に多角形の辺によって形成されるハミルトン閉路を含みます。与えられたグラフを可視グラフとし、指定されたハミルトン閉路を辺の閉路とする多角形を再構築する計算複雑度は未解決問題です。^{[ 39 ]}

• カーペンターのルール問題、単純多角形から凸多角形への連続的な移動に関する問題
• エルデシュ・ナジの定理とは、非凸な単純多角形のポケットを反転させて凸にするプロセスである。
• ネット（多面体）：折り畳んで接着することで特定の多面体を形成できる単純な多角形。
• 球面多角形とは、球面上における類似の概念である。
• 弱単純多角形とは、辺が限られた方法で接触することを許容する単純多角形の一般化である。

• ワイススタイン、エリック W. 「単純多角形」 . MathWorld .