Loading article…
離散幾何学と計算幾何学において、単純多角形の凸包は、与えられた単純多角形を含む最小周囲長の多角形です。これは、凸包のより一般的な概念の特殊なケースです。これは線形時間で計算でき、点集合の凸包のアルゴリズムよりも高速です。
単純な多角形の凸包は、与えられた多角形自体と、単一の凸包の辺を持つ多角形の多角形チェーンによって囲まれた多角形のポケットに分割できます。この凸包の辺を横切って任意に選択したポケットを繰り返し反射すると、より大きな単純な多角形のシーケンスが生成されます。エルデシュ・ナジの定理によれば、このプロセスは最終的に凸多角形で終了します。
構造
単純多角形の凸包はそれ自体が凸多角形である。元の単純多角形をその凸包に重ねると、この凸多角形は領域に分割され、そのうちの 1 つが元の多角形である。残りの領域はポケットと呼ばれる。各ポケット自体は単純多角形であり、与えられた単純多角形の境界上の多角形チェーンと凸包の単一の辺によって囲まれる。すでに凸である多角形にはポケットはない。[1]
このように多角形の包とポケットを構築し、各ポケットに対して同じタイプの階層を再帰的に形成することで、任意の多角形の階層的な記述を形成できます。[1]この構造は凸差分木と呼ばれ、効率的に構築できます。[2]
アルゴリズム
単純な多角形の凸包を求めることは線形時間で実行できる。この問題に関する初期の発表のいくつかは誤りであることが判明したが、その多くは交差を伴う中間状態をもたらし、それが破綻したためである。この問題に対する最初の正しい線形時間アルゴリズムは McCallum と Avis (1979) によって提示された。[3]その発表後も、他の誤ったアルゴリズムが発表され続けた。[4] Brönnimann と Chan (2006) は、この問題に対して発表されたアルゴリズムの大部分が誤りであると述べているが[5]、 Greg Aloupis が収集した後の歴史では、15 のアルゴリズムのうち 7 つだけが誤りであるとされている。[6]
この問題に対する特に単純なアルゴリズムが、Graham & Yao (1983) および Lee (1983) によって発表されました。点集合の凸包に対するGraham スキャンアルゴリズムと同様に、このアルゴリズムはスタック データ構造に基づいています。このアルゴリズムは、凸包上にあることがわかっている頂点 (たとえば、最も左の点) から始めて、時計回りの順序で多角形を走査します。走査する際に、ポケット内にあることがまだ識別されていない頂点の凸シーケンスをスタックに格納します。このシーケンス内の点は、一部のエッジにポケットが付いている可能性のある凸多角形の頂点 (必ずしもこれまでに見たすべての頂点の包とは限りません) です。各ステップで、アルゴリズムはスタックの最上部から、スタックの最上部に隣接する 2 つのポケットのいずれにも属さない次の頂点まで、多角形に沿ったパスをたどります。次に、スタックの一番上の 2 つの頂点とこの新しい頂点が凸位置にない間に、スタックをポップし、最後に新しい頂点をスタックにプッシュします。時計回りのトラバーサルが開始点に到達すると、アルゴリズムが完了し、スタックには時計回りの順序で凸包の頂点が含まれます。アルゴリズムの各ステップでは、頂点をスタックにプッシュするか、スタックからポップします。各頂点は最大で 1 回プッシュおよびポップされるため、アルゴリズムの合計時間は線形です。[7] [8]入力頂点が時計回りの順序で配列で指定されている場合、中間ストレージとして定数個の追加変数のみを使用して、出力を同じ配列で返すことができます。[5]
同様の方法は、平面上の部分的に滑らかな閉曲線の凸包を作成するためにも使用できます。 [9]スタックの代わりにデキューを 使用することで、同様のアルゴリズムを任意の多角形チェーンの凸包に一般化することができ、単純な多角形のアルゴリズムは、開始頂点として端点を必要とせず、多角形の任意の頂点から開始できます。[10]
ポケットをひっくり返す
ポケットのフリップは、ポケットの境界となる多角形チェーンをポケットの凸包エッジに反射させることで、与えられた多角形から新しい多角形を構築する。フリップごとに、周囲が等しく面積が大きい別の単純な多角形が生成されるが、同時に複数回フリップすると交差が生じる可能性がある。任意に選択したポケットをフリップし、次に連続して形成された多角形のポケットでこのプロセスを繰り返すと、単純な多角形のシーケンスが生成される。エルデシュ・ナジの定理によれば、このフリッププロセスは最終的に凸多角形に到達して終了する。凸包構築の問題と同様に、この問題には誤った証明の長い歴史がある。[11]
参考文献
- ^ ab Tor, SB; Middleditch, AE (1984)、「単純な多角形の凸分解」、ACM Transactions on Graphics、3 (4): 244–265、doi : 10.1145/357346.357348
- ^ Rappoport, Ari (1992)、「単純な多角形の凸差分木を構築するための効率的な適応アルゴリズム」、Computer Graphics Forum、11 (4): 235–240、doi :10.1111/1467-8659.1140235、S2CID 20137707
- ^ McCallum, Duncan; Avis, David (1979)、「単純な多角形の凸包を見つけるための線形アルゴリズム」、Information Processing Letters、9 (5): 201–206、doi :10.1016/0020-0190(79)90069-3、MR 0552534
- ^ Toussaint, Godfried (1991)、「多角形の凸包アルゴリズムの反例」、パターン認識、24 (2): 183–184、Bibcode :1991PatRe..24..183T、doi :10.1016/0031-3203(91)90087-L、MR 1087740
- ^ ab Brönnimann, Hervé; Chan, Timothy M. (2006)、「単純な多角形の凸包を線形時間で計算するための空間効率の良いアルゴリズム」、計算幾何学、34 (2): 75–82、doi : 10.1016/j.comgeo.2005.11.005、MR 2222883
- ^ Aloupis, Greg、「単純な多角形に対する線形時間凸包アルゴリズムの歴史」、マギル大学、 2020 年 1 月 1 日取得
- ^ グラハム、ロナルド L. ;ヤオ、F. フランシス(1983)、「単純な多角形の凸包を見つける」、アルゴリズムジャーナル、4 (4): 324–331、doi :10.1016/0196-6774(83)90013-5、MR 0729228
- ^ Lee, DT (1983)、「単純な多角形の凸包の発見について」、International Journal of Computer and Information Sciences、12 (2): 87–98、doi :10.1007/BF00993195、MR 0724699、S2CID 28600832
- ^ Schäffer, Alejandro A.; Van Wyk, Christopher J. (1987)、「区分的に滑らかな Jordan 曲線の凸包」、Journal of Algorithms、8 (1): 66–94、doi :10.1016/0196-6774(87)90028-9、MR 0875326
- ^ Melkman, Avraham A. (1987)、「単純なポリラインの凸包のオンライン構築」、Information Processing Letters、25 (1): 11–12、doi :10.1016/0020-0190(87)90086-X、MR 0896397
- ^ Demaine, Erik D. ; Gassend, Blaise; O'Rourke, Joseph ; Toussaint, Godfried T. (2008)、「すべての多角形は有限に反転します...正しいですか?」、離散幾何学と計算幾何学に関する調査、Contemporary Mathematics、vol. 453、プロビデンス、ロードアイランド州: アメリカ数学会、pp. 231–255、doi :10.1090/conm/453/08801、MR 2405683