凸包アルゴリズムのソースを表示

'''凸包アルゴリズム'''（とつほうアルゴリズム）は、[[凸包]]を求める[[アルゴリズム]]である。[[数学]]や[[計算機科学|コンピューターサイエンス]]で[[凸包#応用|幅広い用途]]がある。

[[計算幾何学]]では、さまざまな[[計算複雑性理論|計算複雑性]]を持つ、有限の点のセットの凸包を計算するためのアルゴリズムが考案されている。

凸包アルゴリズムの計算量は、通常は入力の点の数である ''n に依存し''、また凸包上の点の数である ''h に依存する''こともある。

== 平面の場合 ==
アルゴリズムへの入力が[[直交座標系]]上の有限個の順序なしの点の[[集合]]である場合の一般的なケースを考える。

すべての点が同一線上ある場合以外では、それらの凸包は[[凸多角形]]であり、それらの頂点は入力セット内の点である。その最も一般的な表現は、時計回りまたは反時計回りに境界に沿って並べられた頂点のリストである。一部のアプリケーションでは、凸多角形を一連の{{仮リンク|半平面|en|half-planes|label=半平面}}の交点として表すことが向いている。

=== 計算量の下限 ===
平面内の有限の点の集合の場合、凸多角形として表される凸包を見つける[[計算複雑性]]は、[[還元 (計算複雑性理論)|還元]]を使って[[ソート]]以上であることが簡単に示せる。数値の集合 <math>x_1,\dots,x_n</math> について、 <math>(x_1, x^2_1),\dots,(x_n, x^2_n)</math> で表される平面上の点の集合を考える。それらは[[凸関数|凸曲線]]である[[放物線]]上にあるため、凸包の頂点が境界に沿って移動すると、番号のソートされた順序が生成されることが簡単にわかる。<math>x_1,\dots,x_n</math> 。明らかに、記述された数値のポイントへの変換と、それらのソートされた順序の抽出には[[線形時間]]が必要である。したがって、一般的なケースでは、 凸包はソートよりも速く計算できない。

ソートで標準とされる Ω（''n'' log ''n''）の下限は、[[決定木]]モデル内で証明されています。[[決定木]]モデルは数値比較のみを実行でき、[[算術演算]]は実行できないもので、凸包は算出できない。凸包に適したモデルである{{仮リンク|代数決定木|en|algebraic decision tree|label=代数決定木}}モデルでも、ソートには Ω（''n'' log ''n''）時間が必要であり、このモデルでは凸包にも Ω（''n'' log ''n''）時間が必要である<ref name="ps">Preparata, Shamos, ''Computational Geometry'', Chapter "Convex Hulls: Basic Algorithms"</ref>。ただし、たとえば{{仮リンク|整数のソート|en|integer sorting|label=整数のソート}}アルゴリズムを使用して、数値を ''O''（''n'' log ''n''）時間よりも速く並べ替えることができるコンピューター演算のモデルでは、平面凸包もより速く計算できる。例えば、凸包の{{仮リンク|グラハムスキャン|en|Graham scan|label=グラハムスキャン}}アルゴリズムは1回のソートと線形時間の処理で実現される。

=== 最良の出力依存アルゴリズム ===
上記のように、入力サイズ ''n'' の凸包を見つける計算量は、Ω（''n'' log ''n''）を下限とする。ただし、一部の凸包アルゴリズムの計算量は、入力サイズ ''n''と出力サイズ ''h'' （凸包上の点の数）の両方で決まる。このようなアルゴリズムは、{{仮リンク|出力依存アルゴリズム|en|output-sensitive algorithm|label=出力依存アルゴリズム}}と呼ばれる。''h'' = ''o（n''）の場合、これらは、Θ（''n'' log ''n''）アルゴリズムよりも漸近的に効率的と考えられる。

出力依存の凸包アルゴリズムの最悪時間計算量の下限は、平面の場合で Ω（''n'' log ''h''）であることが確立された。<ref name="ps">Preparata, Shamos, ''Computational Geometry'', Chapter "Convex Hulls: Basic Algorithms"</ref>この最良の[[アルゴリズム解析|時間計算量]]を達成するアルゴリズムは複数ある。最初のものは、1986年にカークパトリックとサイデルによって発見された（彼らはそれを「{{仮リンク|究極の凸包アルゴリズム|en|ultimate convex hull algorithm|label=究極の凸包アルゴリズム}}」と呼んだ）。1996年には、さらに単純なアルゴリズム、{{仮リンク|チャンのアルゴリズム|en|Chan's algorithm|label=チャンのアルゴリズム}}がチャンによって開発された。

=== アルゴリズム ===
[[File:GrahamScanDemo.gif|200px|thumb|グラハムスキャンで二次元の凸包を見つける過程。]]
既知の凸包アルゴリズムを公開順に並べている。各アルゴリズムの時間計算量は、入力点の数 ''n'' と凸包上の点の数 ''h'' で表される。最悪の場合では、 ''h'' は ''n'' と同じ大きさになる可能性がある。
* '''[[ギフト包装法]]'''、別名: '''ジャービス行進''' — ''O''（''nh''）<br />最も単純な（しかし最悪の場合の時間効率が良くない）平面アルゴリズムの1つ。1970年にチャンドとカプール、1973年にジャービスによって別々に発見された。[[ランダウの記号|O]]（''nh''）の[[アルゴリズム解析|時間計算量]]がかかる。最悪の場合は [[ランダウの記号|Θ]]（''n <sup>2</sup>''）かかる。
* '''{{仮リンク|グラハムスキャン|en|Graham Scan|label=グラハムスキャン}}''' — ''O''（''n'' log ''n''）<br />1972年に[[ロナルド・グラハム]]によって公開された、もう少し洗練された、はるかに効率的なアルゴリズム。座標の1つまたは固定ベクトルに対する角度で、点がソート済みの場合、アルゴリズムには O（''n''）時間がかかる。
* '''{{仮リンク|クイックハル|en|Quickhull|label=クイックハル}}'''<br />1977年にW.エディによって、1978年にA.Bykatによって別々に発見された。[[クイックソート]]アルゴリズムと同様に、期待時間計算量は ''O''（''n'' log ''n''）で、最悪の場合、 ''O''（''n'' <sup>2</sup>）かかる可能性がある。
* '''分割統治法''' — ''O''（''n'' log ''n''）<br />こちらも、O（''n'' log ''n''）アルゴリズム。1977年にプレパラータとホンによって公開されました。このアルゴリズムは、3次元の場合にも適用できます。
* '''[[wikibooks:Algorithm Implementation/Geometry/Convex hull/Monotone chain|モノトーンチェーン]]'''、別名: '''アンドリューのアルゴリズム''' — ''O''（''n'' log ''n''）<br />1979年にA.M.アンドリューによって発表された。このアルゴリズムは、点を辞書式に座標で並べ替えるグラハムスキャンの変形と見なすことができる。入力がすでにソートされている場合、 ''O''（''n''）の時間で実行できる。
* '''インクリメンタル凸包アルゴリズム''' — ''O''（''n'' log ''n''）<br />1984年にマイケル・カーライによって発表された。
* '''{{仮リンク|カークパトリック-サイデルアルゴリズム|en|Kirkpatrick–Seidel algorithm|label=カークパトリック-サイデルアルゴリズム}}''' — ''O''（''n'' log ''h''）<br />最初の最適な出力依存ｎアルゴリズム。分割統治アルゴリズムに、征服前の結婚（marriage-before-conquest）と{{仮リンク|低次元線形計画法|en|low-dimensional linear programming|label=低次元線形計画法}}による変更を加えたもの。1986年にカークパトリックとサイデルによって発表された。
* '''{{仮リンク|チャンのアルゴリズム|en|Chan's algorithm|label=チャンのアルゴリズム}}''' — ''O''（''n'' log ''h''）<br />1996年にチャンによって作成されたより単純で最適な出力依存のアルゴリズム。これは、ギフト包装法と小さな入力のサブセットに対する ''O''（''n'' log ''n''）アルゴリズム（グラハムスキャンなど）の実行を組み合わせたもの。

=== アクル-トゥーサンヒューリスティック ===
このシンプルな[[ヒューリスティック]]は、凸包アルゴリズムの実装の最初のステップとして、パフォーマンスを向上させるためによく使われる。これは、1978年のセリム・アクルと G.T.トゥーサンによる効率的な凸包アルゴリズムをベースとしている。とにかく凸包の一部ではない多くの点をすばやく除外するというアイデアである。この方法ではまず、x 座標が最低と最高の2つの点と、 y 座標が最低と最高の2つの点を見つける（これらの各操作は [[ランダウの記号|O]]（''n''）となる）。これらの4つの点は凸四角形を形成し、この4点以外のこの四角形内のすべての点は凸包の一部ではない。この四角形にあるこれらすべての点を見つけることも O（''n''）であり、したがって、操作全体は O（''n''）となる。必要に応じて、 x 座標と y 座標の合計が最小および最大の点、および x 座標と y 座標の差が最小および最大の点も追加して、不規則な凸八角形を形成して除外を行います。点が確率変数となる場合、つまり現実でよくあるケースで、この除外処理によって、凸包アルゴリズムが線形時間で完了することが期待される<ref>[[Luc Devroye]] and [[Godfried Toussaint]], "A note on linear expected time algorithms for finding convex hulls," ''Computing'', Vol. 26, 1981, pp. 361-366.</ref>。

=== オンライン／動的凸包問題 ===
これまでの説明では、すべての入力ポイントが事前にわかっている場合を想定していたが、他の2つのシチュエーションを想定することもできる<ref name="ps">Preparata, Shamos, ''Computational Geometry'', Chapter "Convex Hulls: Basic Algorithms"</ref>。

* '''オンライン凸包問題'''：入力点は1つずつ順番に渡される。各点が入力に到着するたび、これまでに取得した点の集合の凸包を効率的に計算する。
* '''{{仮リンク|動的凸包|en|Dynamic convex hull|label=動的凸包}}のメンテナンス'''：入力点を順番に追加または削除できる。凸包を、追加/削除操作のたびに更新する必要がある。

点を追加すると、凸包の頂点の数が最大で1増える可能性があり、削除すると、 ''n'' 頂点の凸包が ''n - 1'' 頂点に変換される可能性がある。

オンライン凸包問題は、点ごとにO（log ''n''）で処理できる。これは、漸近的に最適である。動的凸包は、操作ごとに O（log <sup>2</sup> ''n''）で処理できる<ref name="ps">Preparata, Shamos, ''Computational Geometry'', Chapter "Convex Hulls: Basic Algorithms"</ref>。

=== 単純多角形 ===
[[File:Convex hull of a simple polygon.svg|thumb|単純多角形（青）に対する凸包。4つのポケット（黄色）を持つ。青と黄色の両方を合わせた領域が凸包である。]]

単純多角形（自己交差を持たない多角形）の凸包は、その多角形によって複数の多角形に分割されている。そのうちの1つは多角形自体であり、残りは多角形境界の断片と凸包の一辺で囲まれた''ポケット''である。単純多角形の凸包を構築する問題について多くのアルゴリズムが公開されていたが、それらのほぼ半分は正しくなかった<ref>{{Cite web |url=http://cgm.cs.mcgill.ca/~athens/cs601/ |title=A History of Linear-time Convex Hull Algorithms for Simple Polygons |author=Aloupis |first=Greg |accessdate=October 11, 2020}}</ref>。マッカラムとエイビスは最初の正しいアルゴリズムを提供した<ref>{{Citation|title=A linear algorithm for finding the convex hull of a simple polygon|last=McCallum|first=Duncan|last2=Avis|first2=David|author2-link=David Avis|year=1979|journal=[[Information Processing Letters]]|volume=9|number=5|pages=201–206|doi=10.1016/0020-0190(79)90069-3|mr=552534}}</ref>。{{Harvtxt|グラハム|ヤオ|1983}}、あるいは{{Harvtxt|リー|1983}} による簡略版では、単一の[[スタック|スタックデータ構造]]のみを使用する。彼らのアルゴリズムは、多角形の左端の頂点から時計回りにたどる。その際、まだポケットの中に位置すると判明してない頂点を格納していき、スタック上に凸多角形状の点のリストを作る。この各ステップでは、スタックのトップの点から、それと隣接するポケットではない頂点まで、多角形にそった経路をたどる。そしてこの新しい頂点とスタックの上から2つの頂点が凸状の形にならない場合、スタックのポップをしてから、最後に新しい頂点を追加する。時計回りの処理が開始点に達すると、このスタック内の頂点列が凸包となる<ref>{{Citation|title=Finding the convex hull of a simple polygon|last=Graham|first=Ronald L.|author-link=Ronald Graham|last2=Yao|first2=F. Frances|author2-link=Frances Yao|year=1983|journal=[[Journal of Algorithms]]|volume=4|number=4|pages=324–331|doi=10.1016/0196-6774(83)90013-5|mr=729228}}</ref><ref>{{Citation|title=On finding the convex hull of a simple polygon|last=Lee|first=D. T.|year=1983|journal=International Journal of Computer and Information Sciences|volume=12|number=2|pages=87–98|doi=10.1007/BF00993195|mr=724699}}</ref>。

== 高次元 ==
3次元の場合や、任意の次元の場合でも、多くのアルゴリズムが知られている<ref>See [[David Mount]]'s [http://www.cs.umd.edu/~mount/754/Lects/754lects.pdf Lecture Notes], including Lecture 4 for recent developments, including
[[Chan's algorithm]].</ref>。チャンのアルゴリズムは2次元と3次元に、クイックハルは高次元の凸包の計算に使用できる<ref>{{Cite journal|last=Barber|first=C. Bradford|last2=Dobkin, David P.|last3=Huhdanpaa, Hannu|date=1 December 1996|title=The quickhull algorithm for convex hulls|journal=ACM Transactions on Mathematical Software|volume=22|issue=4|pages=469–483|DOI=10.1145/235815.235821}}</ref>。

有限個の点の集合の場合、凸包は3次元では入力の点の集合の一部から成る凸多面体、任意の次元では凸[[ポリトープ]]である。ただし、その表現は平面の場合ほど単純ではない。高次元では、凸ポリトープの頂点がわかっている場合でも面を作成するのは自明ではないし、面から頂点を作成するのも自明ではない。出力面の情報のサイズは、入力頂点のサイズよりも指数関数的に大きくなる可能性があり、入力と出力の両方が同等のサイズである場合でも、高次元の凸包の既知のアルゴリズムは、入力の縮退の問題と非常に複雑な中間結果に関する問題の両方の理由から出力依存ではない<ref>{{Citation|title=How good are convex hull algorithms?|last=Avis|first=David|author-link=David Avis|last2=Bremner|first2=David|last3=Seidel|first3=Raimund|author3-link=Raimund Seidel|year=1997|journal=[[Computational Geometry (journal)|Computational Geometry: Theory and Applications]]|volume=7|number=5–6|pages=265–301|doi=10.1016/S0925-7721(96)00023-5}}.</ref>。

== 関連項目 ==

* [[直交凸包]]

== 出典 ==
{{Reflist}}

== 参考文献 ==

* [[:en:Thomas_H._Cormen|Thomas H. Cormen]], [[:en:Charles_E._Leiserson|Charles E. Leiserson]], [[:en:Ronald_L._Rivest|Ronald L. Rivest]], and [[:en:Clifford_Stein|Clifford Stein]]. ''[[:en:Introduction_to_Algorithms|Introduction to Algorithms]]'', Second Edition. MIT Press and McGraw-Hill, 2001. {{ISBN2|0-262-03293-7}}. Section 33.3: Finding the convex hull, pp.&nbsp;947&#x2013;957.
* [[:en:Franco_P._Preparata|Franco P. Preparata]], [[:en:S.J._Hong|S.J. Hong]]. ''Convex Hulls of Finite Sets of Points in Two and Three Dimensions'', Commun. ACM, vol. 20, no. 2, pp.&nbsp;87&#x2013;93, 1977.
* {{Cite book|author=Mark de Berg|author-link=Mark de Berg|author2=Marc van Kreveld|author2-link=Marc van Kreveld|author3=Mark Overmars|author3-link=Mark Overmars|author4=Otfried Schwarzkopf|author4-link=Otfried Schwarzkopf|name-list-style=amp|year=2000|title=Computational Geometry|publisher=[[Springer-Verlag]]|edition=2nd revised|isbn=978-3-540-65620-3|url-access=registration|url=https://archive.org/details/computationalgeo00berg}} Section 1.1: An Example: Convex Hulls (describes classical algorithms for 2-dimensional convex hulls). Chapter 11: Convex Hulls: pp.&nbsp;235&#x2013;250 (describes a randomized algorithm for 3-dimensional convex hulls due to Clarkson and Shor).

== 外部リンク ==

* {{MathWorld|urlname=ConvexHull|title=Convex Hull}}
* [http://www.cgal.org/Part/ConvexHullAlgorithms 2D, 3D, and dD Convex Hull] in [[:en:CGAL|CGAL]], the Computational Geometry Algorithms Library
* [http://www.qhull.org/ Qhull code for Convex Hull, Delaunay Triangulation, Voronoi Diagram, and Halfspace Intersection]
* [https://web.archive.org/web/20101127013711/http://computacion.cs.cinvestav.mx/~anzures/geom/hull.html Demo as Flash swf], Jarvis, Graham, Quick (divide and conquer) and Chan algorithms
* [http://wayback.vefsafn.is/wayback/20130721095350/http://michal.is/projects/convex-hull-gift-wrapping-method/ Gift wrapping algorithm in C#]


[[Category:アルゴリズム]]
{{DEFAULTSORT:とつほうあるこりすむ}}
[[Category:凸包]]
[[Category:計算幾何学]]
[[Category:数学に関する記事]]