多角形化

計算幾何学では、ユークリッド平面上の有限個の点の多角形化は、与えられた点を頂点とする単純多角形です。 ^{[ 1 ]}多角形化は、多角形化^{[ 2 ]}、単純多角形化^{[ 3 ]}、ハミルトン多角形^{[ 4 ]} 、交差しないハミルトンサイクル^{[ 5 ]}、または交差のない直線エッジスパンニングサイクル^{[ 6 ]}とも呼ばれます。

単一の直線上にないすべての点集合には、少なくとも1つの多角形化が存在し、それは多項式時間で見つけることができます。凸位置にある点については1つだけですが、他の点集合では指数関数的に多くの多角形化が存在する場合があります。いくつかの自然な最適化基準の下で最適な多角形化を見つけることは、巡回セールスマン問題のような特殊なケースを含め、困難な問題です。すべての多角形化を数える複雑さは未だ不明です。

多角形化とは、ユークリッド平面上の与えられた点の集合を頂点とする単純な多角形のことです。多角形は、頂点の巡回順序によって記述することができ、頂点は線分（多角形の辺）によって連続するペアで接続されます。このように定義された多角形は、これらの線分の交点が共通の端点のみである場合に「単純」です。^{[ 2 ]}

一部の著者は、どの 3 つの点も一直線上にない一般位置にある点の多角形化のみを考慮しています。 ^{[ 7 ]}この仮定では、多角形の 2 つの連続するセグメント間の角度は 180° にはなりません。しかし、共線性のある点の集合を考慮する場合、多角形化において一部の点で 180° の角度を持つことが一般的に許容されます。この場合、これらの点はエッジの内部ではなく、頂点とみなされます。^{[ 8 ]}

シュタインハウス（1964）は、一直線上に3点が存在しない有限点集合は単純多角形の頂点を形成することを指摘した。^{[ 10 ]}しかし、一直線上に3点が存在しないという条件は不必要に強い。代わりに、多角形化（180°の角度を許容）が存在するために必要なのは、点がすべて一直線上にないことだけである。そうでない場合、多項式時間で構築可能な多角形化が存在する。多角形化を構築する1つの方法は、任意の点を選択することである。${\displaystyle q}$凸包において​${\displaystyle P}$（必ずしも与え​​られた点の1つとは限りません）。次に、点を放射状に並べます。${\displaystyle q}$（qからの距離で同点を解消する）は、与えられたすべての点を通る星形多角形の巡回順序を生成する。${\displaystyle q}$そのカーネル内で。^{[ 7 ]}中心点の周りを放射状に点をソートするという同じアイデアは、グラハムスキャン凸包アルゴリズムのいくつかのバージョンで使用されており、${\displaystyle O(n\log n)}$時間。^{[ 11 ]} 180°の角度を避ける多角形化は必ずしも存在するとは限りません。たとえば、3 × 3および5 × 5 の正方形グリッドの場合、すべての多角形化は 180° の角度を使用します。^{[ 9 ]}

星形多角形化に加えて、共線でない点の集合はすべて単調多角形である多角形化を持つ。これは、ある直線（これを${\displaystyle x}$基準線に垂直なすべての線が、単一の区間で多角形と交差するか、まったく交差しないかのいずれかである。Grünbaum (1994)の構成は、まず点をその${\displaystyle x}$座標を取得し、2 つの極点を通る線を引きます。点がすべて一直線上にあるわけではないため、この線で囲まれた 2 つの開半平面のうち少なくとも 1 つは空でない必要があります。グリュンバウムは、点のソートされた部分列を介して極点を結ぶ 2 つの単調多角形チェーンを形成します。1 つはこの空でない開半平面内の点用、もう 1 つは残りの点用です。それらの和集合が目的の単調多角形です。ソート手順の後、残りの構築は線形時間で実行できます。^{[ 4 ]}

点の集合が軸平行な辺のみを用いた多角形化を持つかどうかを判定することはNP完全である。 ^{[ 12 ]}しかし、すべての頂点で右折するという追加制約を持つ多角形化は、存在する場合、一意に決定される。点を通る各軸平行線は偶数個の点を通過する必要があり、この多角形化はこの線上の点のペアを交互に結ぶ必要がある。多角形化は時間で見つけることができる。${\displaystyle O(n\log n)}$点を等しい座標でグループ化し、各グループを他の座標でソートすることによって。^{[ 13 ]}任意の点集合に対して、この形式の多角形化を持つ回転は最大で1つであり、この回転は再び多項式時間で見つけることができます。^{[ 14 ]}

最適な多角形化を見つける問題（最適性のさまざまな基準について）は、計算上実行不可能な場合が多い。たとえば、巡回セールスマン問題の解は、与えられた点に対して交差を持たない。したがって、常に最小周長の多角形化となる。^{[ 15 ]}これはNP困難である。同様に、最小または最大の面積を持つ単純な多角形化を見つけることはNP困難であることが知られており、^{[ 3 ]}いくつかの計算努力の対象となっている。^{[ 16 ] [ 17 ]}最大面積は常に凸包の面積の半分より大きく、近似比は2となる。 ^{[ 18 ]}最大周長を持つ単純な多角形化の正確な複雑さ、およびこの問題に対する一定の近似比の存在は不明である。 ^{[ 5 ]}最長辺の長さを最小化する多角形化もNP困難であり、近似比よりも優れた近似値を得ることは困難である。$\displaystyle {\sqrt {3}}}$定数係数近似は知られていない。^{[ 19 ]}

巡回セールスマン問題の最適解ではない場合、交差が生じる可能性がありますが、全長を短縮する局所最適化ステップによってすべての交差を解消することが可能です。各ステップで交差を解消するステップを使用すれば、これを多項式時間で実行できますが、^{[ 20 ]}この制約がない場合、代わりに指数関数的な数のステップを使用する局所最適化シーケンスが存在します。^{[ 21 ]}

最短のバイソニックツアー（与えられた点を通る最小周長の単調多角形）は常に多角形化であり、多項式時間で見つけることができます。^{[ 22 ]}

与えられた点集合のすべての多角形化を数える問題は、 NPの決定問題に関連する計数問題のクラスである#Pに属します。しかし、それが#P 完全であるかどうか、またそうでない場合、その計算複雑度がどの程度であるかは不明です。 ^{[ 23 ] [ 24 ]}点集合が凸位置にある場合に限り、多角形化はちょうど 1 つ存在します。^{[ 1 ]}${\displaystyle n}$多角形化の数が次の通りである点$4.64^n$[ ^{25 ]およびすべての}セット${\displaystyle n}$ポイントは最大で$54.6^n$多角形化。^{[ 6 ]}

平面分離定理を点のラベル付き三角形分割に適用する方法は、点群のすべての多角形分割を数えるために使用できます。${\displaystyle n}$準指数時間内の点、${\displaystyle n^{O({\sqrt {n}})}}$[ ^{26 ]}動的計画法を用いてすべての単調多角形化^を 多項式時間で数えることができ、この計算結果を用いてランダムな単調多角形化を生成することができる。^{[ 27 ]}

すべての多角形化のシステムが、多角形化のエッジの限られた数を変更する局所的な移動の下で連結状態空間を形成できるかどうかは不明である。これが可能であれば、状態空間にグラフ走査を適用することにより、すべての多角形化を生成するアルゴリズムの一部として使用できる。この問題では、多角形化の2つのエッジを削除して他の2つのエッジに置き換えるフリップ、または頂点を共有する2つのエッジを含む3つのエッジを削除して他の3つのエッジに置き換えるVEフリップを考慮するだけでは不十分である。同じ点集合に他の多角形化が存在する場合でも、フリップまたはVEフリップが不可能な多角形化が存在する。^{[ 28 ]}

多角形ラップは、与えられた各点を頂点として 1 回以上使用する弱単純多角形であり、すべての多角形化を含み、局所的な移動によって接続されています。^{[ 2 ]}多角形のもう 1 つのより一般的なクラスである周囲多角形は、与えられた点のいくつかを頂点として持ち、すべての点を囲む単純多角形です。これらも局所的に接続されており、多角形ごとに多項式時間でリストできます。このアルゴリズムは、凸包をルートとし、1 つの頂点を削除することによって得られる他の各周囲多角形の親を持つ多角形のツリーを構築します (多角形の外側に2 つの耳の定理を適用することで可能であることが証明されています)。次に、このツリーに逆検索アルゴリズムを適用して多角形をリストします。この方法の結果として、すべての多角形化を指数時間($2^O(n)$のために${\displaystyle n}$点）と多項式空間。^{[ 29 ]}

古典的な点つなぎパズルでは、点を順番に接続して、交差することなく、予期しない形状を形成します。^{[ 30 ]}巡回セールスマン問題とその変種には多くの応用があります。^{[ 31 ]}多角形化は、散在するデータ点からの等高線の再構築や、画像解析における境界追跡にも応用されています。^{[ 32 ]}

• ジョルダン弧で結ばれる無限個の点の集合に関するデンジョイ・リース定理