凸包

赤い集合の凸包は、青と赤の凸集合です。

幾何学において、ある図形の凸包、凸包、あるいは凸閉包^{[ 1 ]}とは、その図形を含む最小の凸集合のことである。凸包は、ユークリッド空間の与えられた部分集合を含むすべての凸集合の積として定義されるか、あるいはそれと同値として、その部分集合内の点のすべての凸結合の集合として定義される。平面の有界部分集合の場合、凸包は部分集合の周囲に張られた輪ゴムで囲まれた図形として視覚化される。

開集合の凸包は開集合であり、コンパクト集合の凸包はコンパクト集合である。すべてのコンパクト凸集合はその端点の凸包である。凸包演算子は閉包演算子の一例であり、すべての反マトロイドは、この閉包演算子を有限の点集合に適用することで表すことができる。平面またはその他の低次元ユークリッド空間内の有限の点集合の凸包を求めるアルゴリズムの問​​題、および交差する半空間の双対問題は、計算幾何学における基本的な問題である。これらは、2次元または3次元の点集合では1000分で解くことができ、高次元では上界定理で与えられる最悪の出力計算量に匹敵する時間で解くことができる。 ${\displaystyle O(n\log n)}$

凸包は有限点集合だけでなく、単純多角形、ブラウン運動、空間曲線、関数のエピグラフについても研究されてきました。凸包は、数学、統計学、組合せ最適化、経済学、幾何学モデリング、動物行動学など、幅広い分野で応用されています。関連する構造としては、直交凸包、凸層、ドロネー三角形分割とボロノイ図、凸頭蓋骨などがあります。

定義

有界平面集合の凸包：輪ゴムのアナロジー

ユークリッド空間内の点の集合は、その集合の各点の組を結ぶ線分を含むとき、凸であると定義される。与えられた集合の凸包は次のように定義される^{[ 2 ]。}${\displaystyle X}$

1. （唯一の）最小凸集合は、${\displaystyle X}$
2. を含むすべての凸集合の共通部分${\displaystyle X}$
3. 点のすべての凸結合の集合は${\displaystyle X}$
4. 頂点を持つ単体の和集合は${\displaystyle X}$

ユークリッド平面上の有界集合（全てが一直線上にあるわけではない）の場合、凸包の境界は を含む最小周囲長の単純な閉曲線となる。輪ゴムを伸ばして集合全体を囲み、その後放して縮ませることを想像すると、輪ゴムがぴんと張ったときに の凸包を囲むことになる。^{[ 3 ]}この定式化は直ちに高次元には一般化できない。3次元空間内の有限の点集合の場合、点の全域木の近傍は、凸包の表面積よりも小さい任意の小さな表面積でそれらの点を囲む。^{[ 4 ]}しかし、高次元では、与えられた形状の上にある最小エネルギー面を見つける障害問題の変形において、凸包を解として持つことができる。^{[ 5 ]}${\displaystyle X}$ ${\displaystyle S}$ ${\displaystyle S}$

3次元の物体の場合、最初の定義は、凸包は物体の最小の凸包境界体積であると述べている。凸集合の交差を用いた定義は非ユークリッド幾何学に拡張可能であり、凸結合を用いた定義はユークリッド空間から任意の実ベクトル空間またはアフィン空間に拡張可能である。凸包は、より抽象的な方法で、有向マトロイドへと一般化することもできる。^{[ 6 ]}

定義の同等性

120点群の3D凸包

最初の定義が意味を成すかどうかは明らかではありません。なぜ、任意の に対してを含む唯一の最小凸集合が存在するのでしょうか？しかし、2番目の定義、すなわち を含むすべての凸集合の交差は明確に定義されています。交差する集合に が含まれるため、それは を含む他のすべての凸集合の部分集合です。したがって、それはまさに を含む唯一の最小凸集合です。したがって、最初の2つの定義は同等です。^{[ 2 ]}${\displaystyle X}$ ${\displaystyle X}$ ${\displaystyle X}$ ${\displaystyle Y}$ ${\displaystyle X}$ ${\displaystyle Y}$ ${\displaystyle X}$

を含む各凸集合は（凸であるという仮定により） 内の点のすべての凸結合を必ず含むため、すべての凸結合の集合は を含むすべての凸集合の交差に含まれます。逆に、すべての凸結合の集合自体が を含む凸集合であるため、 を含むすべての凸集合の交差も含まれ、したがって 2 番目と 3 番目の定義は同等です。^{[ 7 ]}${\displaystyle X}$ ${\displaystyle X}$ ${\displaystyle X}$ ${\displaystyle X}$ ${\displaystyle X}$

実際、カラテオドリの定理によれば、 が-次元ユークリッド空間の部分集合である場合、 からの有限個の点のすべての凸結合は、内の最大で 個の点の凸結合でもある。 -組の点の凸結合の集合は単体 である。平面では三角形であり、3次元空間では四面体である。したがって、 の点のすべての凸結合は、頂点が に属する単体に属し、3番目と4番目の定義は同値である。^{[ 7 ]}${\displaystyle X}$ ${\displaystyle d}$ ${\displaystyle X}$ ${\displaystyle d+1}$ ${\displaystyle X}$ ${\displaystyle (d+1)}$ ${\displaystyle X}$ ${\displaystyle X}$

上部船体と下部船体

2次元では、凸包は、包の左端と右端の点の間を伸びる上部包と下部包の2つの部分に分割されることがあります。より一般的には、任意の次元の凸包において、包の境界を上向きの点（上向きの射線が包から分離する点）、下向きの点、および端点に分割することができます。3次元の包では、境界の上向きの部分と下向きの部分は位相ディスクを形成します。^{[ 8 ]}

位相的性質

密閉型と開放型の船体

集合の閉じた凸包は凸包の閉包であり、開いた凸包は凸包の内部（またはいくつかの情報源では相対内部）である。 ^{[ 9 ]}

の閉凸包は、を含むすべての閉半空間の交差である。 の凸包自体が既に閉集合である場合（例えば、が有限集合、あるいはより一般的にはコンパクト集合である場合）、それは閉凸包と等しい。しかし、閉半空間の交差はそれ自体が閉じているため、凸包が閉じていない場合は、このように表すことはできない。^{[ 10 ]}${\displaystyle X}$ ${\displaystyle X}$ ${\displaystyle X}$ ${\displaystyle X}$

集合の開凸包が次元である場合、その包のすべての点は最大で の点からなる開凸包に属する。正方形、正八面体、あるいは高次元交差多面体の頂点集合は、まさに 個の点が必要となる例である。^{[ 11 ]}${\displaystyle X}$ ${\displaystyle d}$ ${\displaystyle 2d}$ ${\displaystyle X}$ ${\displaystyle 2d}$

位相特性の保存

アグネーシの魔女。赤い曲線上またはその上の点は、凸包が開いている閉集合（開いた上半平面）の例を示しています。

位相的に、開集合の凸包は常にそれ自身開集合であり、（ユークリッド空間においては）コンパクト集合の凸包は常にそれ自身コンパクト集合である。しかし、凸包が閉じていない閉集合も存在する。^{[ 12 ]}例えば、閉集合

${\displaystyle \left\{(x,y)\mathop {\bigg |} y\geq {\frac {1}{1+x^{2}}}\right\}}$

（アグネシの魔女の上または上にある点の集合）は開いた上半平面を凸包として持ちます。^{[ 13 ]}

凸包はより一般的に無限次元位相ベクトル空間において定義できるが、これらの空間ではコンパクト性は保存されない可能性がある。その代わりに、有限次元ユークリッド空間におけるコンパクト集合の凸包のコンパクト性は、クライン・スミュリアン定理によって一般化される。これによれば、バナッハ空間の弱コンパクト部分集合（弱位相の下でコンパクトである部分集合）の閉凸包は弱コンパクトである。^{[ 14 ]}

極端な点

凸集合の端点とは、その集合内の他の2点を結ぶ線分上にない点のことである。凸包の場合、すべての端点は与えられた集合の一部でなければならない。そうでなければ、与えられた点の凸結合として集合を形成できないからである。クライン・ミルマンの定理によれば、ユークリッド空間（またはより一般的には局所凸位相ベクトル空間）のすべてのコンパクト凸集合は、その端点の凸包である。^{[ 15 ]}しかし、コンパクトでない凸集合の場合はこの限りではない。例えば、ユークリッド平面全体と単位開球はどちらも凸であるが、どちらにも端点はない。ショケ理論はこの理論を、端点の有限凸結合から、より一般的な空間における無限結合（積分）へと拡張する。^{[ 16 ]}

幾何学的および代数的性質

閉包演算子

凸包演算子は閉包演算子の特徴的な性質を持つ：^{[ 17 ]}

• これは拡張可能であり、あらゆる集合の凸包がのスーパーセットであることを意味します。${\displaystyle X}$ ${\displaystyle X}$
• これは非減少 であり、と の任意の2 つの集合に対して、 の凸包は の凸包のサブセットであることを意味します。${\displaystyle X}$ ${\displaystyle Y}$ ${\displaystyle X\subseteq Y}$ ${\displaystyle X}$ ${\displaystyle Y}$
• これはべき等性があり、つまり任意の に対して、 の凸包の凸包はの凸包と同じになります。${\displaystyle X}$ ${\displaystyle X}$ ${\displaystyle X}$

有限の点集合に適用すると、これは反マトロイドの閉包作用素、すなわち点集合の殻反マトロイドとなる。あらゆる反マトロイドは、このようにして、十分に高い次元のユークリッド空間における点の凸包によって表現することができる。^{[ 18 ]}

ミンコフスキー和

凸包の構築とミンコフスキー和の演算は互いに可換である。つまり、集合の凸包のミンコフスキー和は、同じ集合のミンコフスキー和の凸包と同じ結果を与える。これは、ミンコフスキー和とその凸包の距離を定めるシャプレー・フォークマン定理への一歩となる。 ^{[ 19 ]}

射影的双対性

点集合の凸包を構築するための射影双対演算は、原点（または任意の指定された点）をすべて含む閉じた半空間の族の交差を構築することである。^{[ 20 ]}

特殊なケース

有限点集合

平面上の点の凸包

有限点集合の凸包は、のとき凸多角形を形成し、より一般的にはの凸多面体を形成する。 包の各端点は頂点と呼ばれ、（クライン・ミルマンの定理により）すべての凸多面体はその頂点の凸包である。 は、 の頂点が に属し、 のすべてを囲む唯一の凸多面体である。^{[ 3 ]}一般的な位置 にある点の集合に対して、凸包は単体多面体である。^{[ 21 ]}${\displaystyle S\subset \mathbb {R} ^{d}}$ ${\displaystyle d=2}$ ${\displaystyle \mathbb {R} ^{d}}$ ${\displaystyle S}$ ${\displaystyle S}$

上界定理によれば、次元ユークリッド空間における点の凸包の面の数はである。^{[ 22 ]}特に、2次元および3次元では、面の数は において最大で線形である。^{[ 23 ]}${\displaystyle n}$ ${\displaystyle d}$ ${\displaystyle O(n^{\lfloor d/2\rfloor })}$ ${\displaystyle n}$

単純な多角形

単純な多角形（青色）の凸包（青色と黄色）

単純多角形の凸包は与えられた多角形を囲み、それによって領域に分割されます。そのうちの1つは多角形自体です。多角形の多角形連鎖と単一の凸包辺で囲まれた他の領域はポケットと呼ばれます。各ポケットに対して同じ分解を再帰的に計算すると、与えられた多角形の凸差分木と呼ばれる階層的な記述が形成されます。^{[ 24 ]}ポケットを凸包辺で反射すると、与えられた単純多角形は同じ周囲長で面積の大きい多角形に拡張され、エルデシュ・ナジの定理によれば、この拡張プロセスは最終的に終了します。^{[ 25 ]}

ブラウン運動

平面上のブラウン運動によって生成される曲線は、任意の固定時刻において、連続的に微分可能な曲線 を境界とする凸包を持つ確率が 1 である。しかし、範囲 内の任意の角度に対して、ブラウン運動中に運動粒子が角度 の点で凸包の境界に接する時刻が存在する。この例外的な時刻の集合のハウスドルフ次元は（高い確率で） である。^{[ 26 ]}${\displaystyle \theta}$ ${\displaystyle \pi /2<\theta <\pi }$ ${\displaystyle \theta}$ ${\displaystyle 1-\pi /2\theta }$

空間曲線

オロイド、3次元空間における2つの円の凸包

3次元空間に一般に配置された空間曲線または有限の空間曲線の凸包では、曲線から離れた境界部分は展開可能な面と線織面になります。^{[ 27 ]}例としては、直交する平面にある2つの円が互いの中心を通る凸包であるオロイド、 ^{[ 28 ]}直交する平面にある2つの半円が共通の中心を持つ凸包であるスフェリコン、およびアレクサンドロフの一意性定理から得られる、周囲長が等しい2つの平面凸集合を貼り合わせてできる曲面の凸形状であるD形式などがあります。 ^{[ 29 ]}

機能

実ベクトル空間上の関数の凸包あるいは下凸包とは、そのエピグラフが のエピグラフの下凸包である関数のことである。これはによって主となる唯一の極大凸関数である。^{[ 30 ]}この定義は関数の集合の凸包（それらのエピグラフの和集合の凸包から得られる、あるいは同値としてそれらの点ごとの最小値から得られる）に拡張することができ、この形式では凸共役演算と双対である。^{[ 31 ]}${\displaystyle f}$ ${\displaystyle f}$ ${\displaystyle f}$

計算

計算幾何学では、有限の点集合やその他の幾何学的対象に対する凸包を計算するアルゴリズムが数多く知られている。凸包を計算するということは、要求される凸形状の明確で効率的な表現を構築することを意味する。点集合の凸包の出力表現としては、包の面を記述する線型不等式のリスト、面とその隣接関係の無向グラフ、あるいは包の全面格子などが考えられる。 ^{[ 32 ]} 2次元では、頂点となる点を、包の周りの巡回順序でリストするだけで十分である。^{[ 3 ]}

2次元または3次元の凸包の場合、対応するアルゴリズムの複雑度は通常、（入力点の数）と、（凸包上の点の数）で推定され、これは よりも大幅に小さくなることがあります。より高次元の包の場合、他の次元の面の数も分析に含まれることがあります。グラハムスキャンは、時間 で平面上の点の凸包を計算できます。2次元および3次元の点の場合、時間 で凸包を計算する、より複雑な出力依存アルゴリズムが知られています。これらには、 ChanのアルゴリズムとKirkpatrick–Seidelアルゴリズムが含まれます。^{[ 33 ]}次元の場合、凸包の計算時間は で、問題の最悪ケースの出力複雑度と一致します。^{[ 34 ]}平面上の単純な多角形の凸包は、線形時間で構築できます。^{[ 35 ]}${\displaystyle n}$ ${\displaystyle h}$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle O(n\log n)}$ ${\displaystyle O(n\log h)}$ ${\displaystyle d>3}$ ${\displaystyle O(n^{\lfloor d/2\rfloor })}$

動的凸包データ構造は、点の挿入や削除が行われる点の集合の凸包を追跡するために使用できます。^{[ 36 ]}また、運動凸包構造は、連続的に移動する点の凸包を追跡できます。^{[ 37 ]}凸包の構築は、点集合の幅と直径を計算する回転ノギス法 など、他の多くの計算幾何学アルゴリズムのツール、つまり構成要素としても機能します。 ^{[ 38 ]}

関連する構造

直交凸包

相対凸包

凸包と同様に、点の集合から他の形状を定義できます。例えば、ある性質を持つ最小の上位集合、特定の形状族に属する点を含むすべての形状の積集合、あるいは特定の組み合わせにおけるすべての点の組み合わせの和集合などです。例えば、

• アフィン包は、与えられた集合を含むユークリッド空間の最小のアフィン部分空間、またはその集合内の点のすべてのアフィン組み合わせの和集合である。^{[ 39 ]}
• 線形包は、与えられた集合を含むベクトル空間の最小の線形部分空間、またはその集合内の点のすべての線形結合の和集合である。^{[ 39 ]}
• ベクトル空間の部分集合の円錐包または正包は、その部分集合内の点のすべての正の組み合わせの集合である。^{[ 39 ]}
• 3次元物体の視包は、複数の視点からの視点において、ある視点からのすべての光線が物体と交差する点群から構成される。これは、各視点における物体の輪郭線によって生成される（非凸）円錐の交点と等価である。視包は、 3次元再構成において、与えられた視点から同じ輪郭線を持つ最大の形状として用いられる。 ^{[ 40 ]}${\displaystyle p}$ ${\displaystyle p}$
• 平面の部分集合の円形包またはアルファ包は、その部分集合を含む、与えられた半径を持つすべての円板の交差である。^{[ 41 ]}${\displaystyle 1/\alpha }$
• 2次元単純多角形の部分集合の相対凸包は、すべての相対凸集合の交差であり、同じ多角形内の集合は、その任意の2点間の測地線を含む場合、相対凸包となる。 ^{[ 42 ]}
• 直交凸包または直線凸包は、すべての直交凸包と連結超集合の交差であり、集合がその点のペアの間に軸に平行なすべての線分を含む場合、その集合は直交凸包である。^{[ 43 ]}
• 直交凸包は、より一般的な構成である超凸包の特殊なケースであり、与えられた計量空間の点を含む最小の入射的な計量空間と考えることができる。^{[ 44 ]}
• 正則凸包は、複素解析多様体と同様の概念を一般化したもので、与えられた集合を含む正則関数のサブレベル集合の交差として得られる。 ^{[ 45 ]}

点集合のドロネー三角形分割とその双対であるボロノイ図は、数学的には凸包に関連している。つまり、 における点集合のドロネー三角形分割は、における凸包の射影として見ることができる。^{[ 46 ]}有限点集合の アルファ形状は、異なる詳細レベルで点集合の形状を記述する（非凸）幾何学的オブジェクトの入れ子になった族を与える。各アルファ形状は、外接半径をパラメータアルファと比較して選択された、ドロネー三角形分割のいくつかの特徴の和集合である。点集合自体はこの形状族の一方の端点を形成し、その凸包はもう一方の端点を形成する。^{[ 41 ]}点集合の 凸層は凸多角形の入れ子になった族であり、その最外側は凸包であり、内側の層は凸包の頂点ではない点から再帰的に構築される。^{[ 47 ]}${\displaystyle \mathbb {R} ^{n}}$ ${\displaystyle \mathbb {R} ^{n+1}.}$

多角形の凸頭蓋骨は、その多角形に含まれる最大の凸多角形である。これは多項式時間で求まるが、アルゴリズムの指数は高い。^{[ 48 ]}

アプリケーション

CIE 1931 xy色度図上の各色空間における原色の凸包は、その空間の可能な色の範囲を定義する。

凸包は多くの分野で幅広く応用されています。数学では、凸包は多項式、行列の固有値、ユニタリ要素の研究に使用され、離散幾何学のいくつかの定理は凸包に関係しています。凸包は、ロバスト統計でTukeyの深さの最外郭として使用され、 2 次元データのバグプロット視覚化の一部となり、ランダム決定ルールのリスクセットを定義します。組み合わせ問題の解の指標ベクトルの凸包は、組み合わせ最適化と多面体組み合わせ論の中心です。経済学では、凸包を使用して、経済学の凸性手法を非凸市場に適用できます。幾何学モデリングでは、ベジェ曲線の凸包特性は曲線の交差を見つけるのに役立ち、凸包は船体の測定の一部です。また、動物行動の研究では、凸包は行動圏の標準的な定義に使用されます。

数学

一変数多項式のニュートン多面体と多変数多項式のニュートン多面体は、多項式の項の指数から導かれる点の凸包であり、多項式の漸近挙動とその根の値の解析に使用できます。 ^{[ 49 ]}凸包と多項式は、ガウス・ルーカスの定理でも結びついており、これによれば、多項式の微分根はすべて、多項式の根の凸包内にあります。^{[ 50 ]}

7点を交差凸包を持つ3つの部分集合に分割する。これは、トゥヴェルグの定理により、平面上の任意の7点に対して存在することが保証されている。

スペクトル解析では、正規行列の数値範囲はその固有値の凸包である。^{[ 51 ]} ルッソ・ダイの定理はC*-代数におけるユニタリ元の凸包を記述する。^{[ 52 ]}離散幾何学 では、ラドンの定理とトヴェルグの定理はどちらも、交差する凸包を持つ部分集合への点集合の分割の存在に関するものである。^{[ 53 ]}

点間に線分を含む凸集合の定義と、すべての凸集合の交わりとしての凸包の定義は、ユークリッド空間だけでなく双曲空間にも適用される。しかし、双曲空間では、理想点の集合の凸包を考えることもできる。理想点とは、双曲空間自体には属さないが、その空間のモデルの境界上にある点である。3次元双曲空間の理想点の凸包の境界は、ユークリッド空間の線織面に類似しており、その計量特性は低次元位相幾何学における幾何学化予想において重要な役割を果たす。^{[ 54 ]}双曲凸包は、双曲多様体の標準三角形分割の計算の一部としても使用され、結び目の同値性を決定するために適用されている。^{[ 55 ]}

凸包のこの主題への応用についてはブラウン運動のセクションも参照してください。また、可展面の理論への応用については空間曲線のセクションを参照してください。

統計

バグプロット。外側の影付き領域は凸包、内側の影付き領域は50% Tukeyの深度等高線です。

ロバスト統計において、凸包はバグプロットの主要な構成要素の一つであり、バグプロットは2次元の標本点の広がりを視覚化する手法である。テューキー深度の等高線は、凸包が最も外側に位置する凸集合の入れ子状の族を形成し、バグプロットはこの入れ子状の族から別の多角形、すなわち50%深度の等高線も表示する。^{[ 56 ]}

統計的意思決定理論では、ランダム化意思決定ルールのリスクセットは、その基礎となる決定論的意思決定ルールのリスクポイントの凸包である。^{[ 57 ]}

組み合わせ最適化

組合せ最適化と多面体組合せ論において、中心的な研究対象は、組合せ問題の解の指示ベクトルの凸包である。これらの多面体の面、すなわち多面体を半空間の交差として記述する面を見つけることができれば、線形計画法に基づくアルゴリズムを用いて最適解を求めることができる。^{[ 58 ]}多目的最適化では、異なる種類の凸包、すなわち解の重みベクトルの凸包も用いられる。各凸包の頂点を見つけて検査することで、重みの任意の準凸組み合わせを最大化することができ、多くの場合、すべての可能な解を検査するよりも効率的である。^{[ 59 ]}

経済

アロー＝ドブリューの一般経済均衡モデルでは、経済主体は凸状の予算集合と凸状の選好を持つと仮定されている。経済学におけるこれらの凸性の仮定は、均衡の存在を証明するために用いることができる。実際の経済データが非凸である場合、凸包をとることで凸状にすることができる。シャプレー＝フォークマンの定理は、大規模市場においてこの近似が正確であり、元の非凸市場に対して「準均衡」をもたらすことを示すために用いることができる。^{[ 60 ]}

幾何学的モデリング

幾何学モデリングにおいて、ベジェ曲線の重要な特性の一つは、曲線がその制御点の凸包内に収まることである。このいわゆる「凸包性」は、例えば、これらの曲線の交差を素早く検出する際に利用できる。^{[ 61 ]}

船体設計の幾何学において、チェーンガースは帆船の大きさを表す尺度であり、船体の断面の凸包を用いて定義されます。これは、凸包を持つ船体を除き、断面の周囲長であるスキンガースとは異なります。 ^{[ 62 ]}

動物行動学

凸包は、動物行動学（動物行動学）では最小凸多角形としてよく知られており、動物が観察された地点に基づいて動物の行動圏を推定する古典的な（おそらく単純すぎる）アプローチである。 ^{[ 63 ]}外れ値によって最小凸多角形が過度に大きくなる可能性があるため、例えばサンプルの目標割合に近い凸層の1つを選択することによって、観測のサブセットのみを含む緩和されたアプローチが採用されてきた。^{[ 64 ]}または、局所凸包法では、点の近傍の凸包を組み合わせることによって採用されてきた。^{[ 65 ]}

量子物理学

量子物理学では、あらゆる量子システムの状態空間（システムを作ることができるすべての方法の集合）は凸包であり、その極点は純粋状態として知られる半正定値演算子であり、その内部点は混合状態と呼ばれる。^{[ 66 ]}シュレーディンガー-HJW定理は、あらゆる混合状態は実際には純粋状態の凸結合として複数の方法で表すことができることを証明している。^{[ 67 ]}

熱力学

マグネシウム-炭素化合物の凸包。^{[ 68 ]} Mg2C3_は下層の殻の上にあるため不安定であると予想される_。

熱力学における凸包は、ジョサイア・ウィラード・ギブス（1873）によって同定されたが^{[ 69 ]} 、この論文は凸包という名称が付けられる以前に発表された。ある物質の複数の化学量論におけるエネルギーの集合において、下側の凸包上の測定値のみが安定する。凸包から点を取り除き、その点から凸包までの距離を計算すると、その点から新しい凸包までの距離がその位相の安定度を表す。^{[ 70 ]}

歴史

平面上の点からなる下凸包は、1676年にアイザック・ニュートンがヘンリー・オルデンバーグに宛てた手紙の中で、ニュートン多角形の形で登場する。 ^{[ 71 ]}「凸包」という用語自体は、ギャレット・バーコフ （1935年）の著作に早くも登場し、ドイツ語の対応する用語は、例えばハンス・ラデマッハーによるケーニヒ （1922年）の書評など、さらに古くから登場している。「凸包」といった用語も、この時期に使用されていた。^{[ 72 ]}ロイド・ダインズによると、1938年までに「凸包」という用語が標準化された。ダインズは、この用語は不適切だと付け加えている。なぜなら、「包」という語の口語的な意味は、図形の表面を指すように思われるが、凸包は表面だけでなく内部も含むからである。^{[ 73 ]}

注記

1. 凸閉包という用語は、凸包が閉包作用素を定義するという事実を指します。しかし、この用語は閉じた凸包を指すためにも頻繁に使用されるため、混同しないようにする必要があります。例えば、 Fan (1959)、p.48を参照してください。
2. ロッカフェラー（1970）、12ページ。
3. de Berg et al. (2008)、p. 3.
4. Williams & Rossignac (2005) 。Douglas Zareの「非凸集合の周長」の回答も参照。MathOverflow、 2014年5月16日。
5. オーバーマン（2007年）。
6. クヌース（1992年）。
7. Rockafellar (1970)、p. 12; Lay (1982)、p. 17。
8. de Berg et al. (2008)、p. 6。包を2つのチェーンに分割するというアイデアは、 Andrew (1979)によるGrahamスキャンの効率的な変種に由来します。
9. ソンタグ (1982) .
10. ロッカフェラー（1970年）、99ページ。
11. シュタイニッツ (1914) ;ガスティン (1947) ;バラニ、カチャルスキー、パッハ (1982)
12. Grünbaum (2003)、p. 16; Lay (1982)、p. 21; Sakuma (1977)。
13. この例はTalman（1977）の注釈2.6に示されています。
14. ホイットリー（1986年）。
15. ケリンとミルマン (1940) ;レイ (1982)、p. 43.
16. オコン（2000） .
17. キセルマン（2002） .
18. 柏原・中村・岡本 (2005) .
19. Krein & Šmulian (1940)、定理3、562〜563ページ; Schneider (1993)、定理1.1.2（2〜3ページ）および第3章。
20. デ・バーグら。 (2008)、p. 254.
21. Grünbaum (2003)、57ページ。
22. デ・バーグら。 (2008)、p. 256.
23. デ・バーグら。 (2008)、p. 245.
24. ラポポート (1992) .
25. Demaine et al. (2008) .
26. クランストン、シュー＆マーチ（1989）。
27. セディク（1981） .
28. Dirnböck & Stachel (1997) .
29. シートン (2017) .
30. ロッカフェラー（1970年）、36ページ。
31. ロッカフェラー（1970年）、149ページ。
32. エイビス、ブレムナー、ザイデル (1997)。
33. デ・バーグら。 (2008)、p. 13.
34. チャゼル (1993) ;デ・バーグら。 (2008)、p. 256.
35. マッカラム＆エイビス (1979) ;グラハムとヤオ (1983) ;リー (1983)。
36. チャン (2012) .
37. バッシュ、ギバス、ハーシュバーガー (1999)。
38. トゥーサン (1983) .
39. ウェスターマン（1976） .
40. ローレンティーニ (1994) .
41. Edelsbrunner、Kirkpatrick、Seidel（1983） .
42. トゥーサン (1986) .
43. オットマン、ソワサロン＝ソイネン、ウッド (1984)。
44. ヘルリッヒ（1992） .
45. ロッシ（1961年）。
46. ブラウン（1979年）。
47. チャゼル（1985年） .
48. チャン＆ヤップ（1986） .
49. アルティン（1967）；ゲルファンド、カプラノフ、ゼレビンスキー（1994）
50. プラソロフ（2004） .
51. ジョンソン（1976年）。
52. ガードナー（1984年）。
53. レイ（1979年）。
54. エプスタイン＆マーデン（1987）。
55. ウィークス (1993) .
56. Rousseeuw、Ruts、Tukey（1999年）。
57. ハリス（1971年）。
58. Pulleyblank (1983) ; 特に定理2.9の後の注釈を参照。
59. 加藤 (1992) .
60. Nicola (2000)特に第16.9節「非凸性と近似均衡」209～210ページを参照。
61. チェンとワン (2003)。
62. メイソン（1908年）。
63. ケルノハン、ギッツェン、ミルスポウ (2001)、p. 137–140;ニルセン、ペダーセン、リンネル (2008)
64. ワートン（1995年）。
65. ゲッツ＆ウィルマーズ（2004年）。
66. リーフェル＆ポラック（2011年）。
67. カークパトリック (2006) .
68. キムら（2019） .
69. ギブス（1873） .
70. Hautier (2014) ; Fultz (2020)
71. ニュートン (1676) ; Auel (2019)、336 ページ、およびEscobar & Kaveh (2020)を参照してください。
72. 例えば、 White (1923) 520ページを参照。
73. ダインズ（1938年） .

参考文献

• Fan, Ky (1959),凸集合とその応用. 1959年夏季講義. アルゴン国立研究所
• アンドリュー、AM（1979）、「2次元凸包のためのもう一つの効率的なアルゴリズム」、情報処理レター、9（5）：216-219、doi：10.1016/0020-0190（79）90072-3
• アルティン、エミール（1967）、「2.5. ニュートンの多角形」、代数的数と代数的関数、ゴードン＆ブリーチ、pp.  37-43、MR  0237460
• アウエル、アッシャー（2019）「グレース・マレー・ホッパーの数学」（PDF）、アメリカ数学会誌、66（3）：330–340、doi：10.1090/noti1810、MR  3889348、S2CID  76650751
• エイビス、デイビッド；ブレムナー、デイビッド；ザイデル、ライムンド（1997）「凸包アルゴリズムの有効性は？」計算幾何学、7（5-6）：265-301、doi：10.1016/S0925-7721（96）00023-5、MR  1447243
• Bárány, Imre ; Katchalski, Meir ; Pach, János (1982) 「定量的ヘリー型定理」アメリカ数学会紀要、86 (1): 109– 114、doi : 10.1090/S0002-9939-1982-0663877-X、JSTOR  2044407、MR  0663877
• Basch, Julien; Guibas, Leonidas J .; Hershberger, John (1999)「モバイルデータのためのデータ構造」Journal of Algorithms , 31 (1): 1– 28, CiteSeerX  10.1.1.134.6921 , doi : 10.1006/jagm.1998.0988 , MR  1670903 , S2CID  8013433
• バーコフ、ギャレット（1935）、「バナッハ空間における値を持つ関数の積分」、アメリカ数学会誌、38（2）：357-378、doi：10.2307/1989687、JSTOR  1989687、MR  1501815
• Brown, KQ (1979)、「凸包からのボロノイ図」、Information Processing Letters、9 (5): 223– 228、doi : 10.1016/0020-0190(79)90074-7、S2CID  44537056
• de Berg, M. ; van Kreveld, M. ; Overmars, Mark ; Schwarzkopf, O. (2008),計算幾何学：アルゴリズムと応用（第3版）、Springer
• Chan, Timothy M. (2012)、「動的凸包に関する3つの問題」、International Journal of Computational Geometry and Applications、22 (4): 341– 364、doi : 10.1142/S0218195912600096、MR  2994585
• Chang, JS; Yap, C.-K. (1986)、「ジャガイモの皮むき問題に対する多項式解」、Discrete & Computational Geometry、1 (2): 155– 182、doi : 10.1007/BF02187692、MR  0834056
• シャゼル、バーナード（1985）「平面集合の凸層について」IEEE Transactions on Information Theory、31（4）：509–517、doi：10.1109/TIT.1985.1057060、MR  0798557
• Chazelle, Bernard (1993)、「任意の固定次元における最適凸包アルゴリズム」（PDF）、離散幾何学と計算幾何学、10 (1): 377– 409、CiteSeerX  10.1.1.113.8709、doi : 10.1007/BF02573985、S2CID  26605267
• 陳 欽宇; 王 国昭 (2003年3月)、「ベジェ曲線のクラス」、コンピュータ支援幾何学設計、20 (1): 29– 39、doi : 10.1016/s0167-8396(03)00003-7
• クランストン、M.; スー、P.; マーチ、P. (1989)「平面ブラウン運動の凸包の滑らかさ」、確率年報、17 (1): 144– 150、doi : 10.1214/aop/1176991500、JSTOR  2244202、MR  0972777
• Demaine, Erik D. ; Gassend, Blaise; O'Rourke, Joseph ; Toussaint, Godfried T. (2008)「すべての多角形は有限に反転する…そうだろ？」『離散幾何学と計算幾何学の概説』Contemporary Mathematics, vol. 453, Providence, Rhode Island: American Mathematical Society, pp.  231– 255, doi : 10.1090/conm/453/08801 , ISBN 978-0-8218-4239-3、MR  2405683
• Dines, LL (1938)、「凸性について」、アメリカ数学月刊誌、45 (4): 199– 209、doi : 10.2307/2302604、JSTOR  2302604、MR  1524247
• Dirnböck, Hans; Stachel, Hellmuth (1997)、「オロイドの開発」(PDF)、Journal for Geometry and Graphics、1 (2): 105– 118、MR  1622664
• エデルスブルンナー、ハーバート；カークパトリック、デイヴィッド・G；ザイデル、ライムンド（1983）「平面上の点集合の形状について」IEEE Transactions on Information Theory、29（4）：551–559、doi：10.1109/TIT.1983.1056714
• エプスタイン, DBA ;マーデン, A. (1987)「双曲空間における凸包、サリバンの定理、そして測定されたプリーツ面」、エプスタイン, DBA (編)『双曲空間の解析的および幾何学的側面』（コベントリー/ダーラム、1984年）、ロンドン数学会講演録シリーズ、第111巻、ケンブリッジ：ケンブリッジ大学出版局、pp.  113– 253、MR  0903852
• エスコバール、ローラ; カヴェ、キウマーズ (2020年9月)、「凸多面体、代数幾何学、および組合せ論」(PDF)、アメリカ数学会誌、67 (8): 1116– 1123、doi : 10.1090/noti2137、S2CID  221659506
• フルツ、ブレント（2020年4月）、材料の相転移、ケンブリッジ大学出版局、p.55、doi：10.1017/9781108641449、ISBN 9781108641449
• ガードナー、L.テレル（1984）、「ルッソ・ダイ定理の基本的証明」、アメリカ数学会紀要、90（1）：171、doi：10.2307/2044692、JSTOR  2044692、MR  0722439、S2CID  119501393
• ゲルファンド, イムズ州;カプラノフ, ミネソタ州; Zelevinsky、AV (1994)、「6. Newton Polytopes および Chow Polytopes」、Discriminants、Resultants、および MultiDimensional Determinants、Mathematics: Theory & Applications、Birkhäuser、pp.  193–213、doi : 10.1007/978-0-8176-4771-1、ISBN 0-8176-3660-9、MR  1264417
• Getz, Wayne M.; Wilmers, Christopher C. (2004)、「生息域と利用分布の局所最近傍凸包構築」(PDF)、Ecography、27 (4)、Wiley: 489– 505、Bibcode : 2004Ecogr..27..489G、doi : 10.1111/j.0906-7590.2004.03835.x、S2CID  14592779
• ギブス、ウィラード・J.（1873）「表面による物質の熱力学的性質の幾何学的表現法」、コネチカット芸術科学アカデミー紀要、2：382-404; J.ウィラード・ギブスの科学論文集、第1巻：熱力学、ロングマンズ・グリーン社、1906年、33～54頁に再録
• グラハム、ロナルド・L. ;ヤオ、F. フランシス(1983)、「単純多角形の凸包の探索」、アルゴリズムジャーナル、4 (4): 324– 331、doi : 10.1016/0196-6774(83)90013-5、MR  0729228
• Grünbaum, Branko (2003), Convex Polytopes , Graduate Texts in Mathematics, vol. 221 (第2版), Springer, ISBN 9780387004242
• ガスティン、ウィリアム（1947）「ユークリッド集合の凸包の内部について」アメリカ数学会報、53（4）：299-301、doi：10.1090/S0002-9904-1947-08787-5、MR  0020800
• Harris, Bernard (1971)、「統計的意思決定理論のための数学モデル」（PDF）、統計における最適化手法（オハイオ州立大学シンポジウム、オハイオ州コロンバス、1971年）、pp.  369– 389、MR  0356305 、 2021年2月28日にオリジナル（PDF）からアーカイブ、 2020年1月1日取得
• Hautier, Geoffroy (2014)、「データマイニングによる高スループット結晶構造および化合物予測」、Atahan-Evrenk, Sule; Aspuru-Guzik, Alan (編)、『結晶構造の予測と計算：方法と応用』、Topics in Current Chemistry、vol. 345、Springer International Publishing、pp.  139– 179、doi : 10.1007/128_2013_486、ISBN 978-3-319-05773-6、PMID  24287952; 143ページ参照
• Herrlich, Horst (1992)、「距離空間の超凸包」、一般位相幾何学とその応用に関するシンポジウムの議事録（オックスフォード、1989年）、位相幾何学とその応用、44 ( 1– 3): 181– 187、doi : 10.1016/0166-8641(92)90092-E、MR  1173256
• ジョンソン、チャールズ・R.（1976）、「正規性と数値範囲」、線形代数とその応用、15（1）：89-94、doi：10.1016/0024-3795（76）90080-x、MR  0460358
• 柏原健二; 中村正孝; 岡本良夫 (2005)「抽象凸幾何学のアフィン表現定理」,計算幾何学, 30 (2): 129– 144, CiteSeerX  10.1.1.14.4965 , doi : 10.1016/j.comgeo.2004.05.001 , MR  2107032
• 加藤 直樹 (1992)、「二基準ネットワーク最適化問題」、電子情報通信学会論文誌、E75-A: 321– 329
• カーノハン、ブライアン・J.、ギッツェン、ロバート・A.、ミルズポー、ジョシュア・J.（2001）「動物の空間利用と移動の分析」ミルズポー、ジョシュア、マーズラフ、ジョン・M.（編）『無線追跡と動物の個体群』、アカデミック・プレス、ISBN 9780080540221
• Kim, Sooran; Kim, Kyoo; Koo, Jahyun; Lee, Hoonkyung; Min, Byung Il; Kim, Duck Young (2019年12月)「マグネシウム炭化物における圧力誘起相転移と超伝導」、Scientific Reports、9 (1): 20253、Bibcode : 2019NatSR...920253K、doi : 10.1038/s41598-019-56497-6、PMC  6934831、PMID  31882982
• カークパトリック, KA (2006), 「シュレーディンガー–HJW定理」, Foundations of Physics Letters , 19 (1): 95– 102, arXiv : quant-ph/0305068 , Bibcode : 2006FoPhL..19...95K , doi : 10.1007/s10702-006-1852-1 , S2CID  15995449
• Kiselman, Christer O. (2002)、「凸性理論における作用素の半群」、アメリカ数学会誌、354 (5): 2035– 2053、doi : 10.1090/S0002-9947-02-02915-X、MR  1881029
• Knuth, Donald E. (1992), Axioms and Hulls , Lecture Notes in Computer Science, vol. 606, Heidelberg: Springer-Verlag, doi : 10.1007/3-540-55611-7 , ISBN 3-540-55611-7, MR  1226891 , S2CID  5452191 , 2017年6月20日にオリジナルからアーカイブ、 2011年9月15日取得
• Kőnig、Dénes (1922 年 12 月)、「Über konvexe Körper」、Mathematische Zeitschrift、14 (1): 208–210、doi : 10.1007/bf01215899、S2CID  128041360;ハンス・ラデマッハー（1922）によるレビューも参照、 JFM 48.0835.01 
• クライン、マーク；ミルマン、デイヴィッド（1940）「正則凸集合の極点について」、数学研究、9：133-138、doi：10.4064/sm-9-1-133-138
• Krein, M. ; Šmulian, V. (1940) 「バナッハ空間に共役な空間内の規則凸集合について」Annals of Mathematics , Second Series, 41 (3): 556– 583, doi : 10.2307/1968735 , hdl : 10338.dmlcz/100106 , JSTOR  1968735 , MR  0002009
• Laurentini, A. (1994)、「シルエットベースの画像理解のための視覚的包概念」、IEEE Transactions on Pattern Analysis and Machine Intelligence、16 (2): 150– 162、doi : 10.1109/34.273735
• レイ、スティーブン・R.（1982）、凸集合とその応用、ジョン・ワイリー・アンド・サンズ、ISBN 0-471-09584-2、MR  0655598
• Lee, DT (1983)、「単純多角形の凸包の発見について」、International Journal of Computer and Information Sciences、12 (2): 87– 98、doi : 10.1007/BF00993195、MR  0724699、S2CID  28600832
• メイソン、ハーバート・B.（1908年）『船舶・海運百科事典』 698ページ
• マッカラム、ダンカン;エイビス、デイヴィッド(1979)、「単純多角形の凸包を求める線形アルゴリズム」、情報処理レター、9 (5): 201– 206、doi : 10.1016/0020-0190(79)90069-3、MR  0552534
• ニュートン、アイザック（1676年10月24日）、「ヘンリー・オルデンバーグへの手紙」、ニュートン・プロジェクト、オックスフォード大学
• ニコラ・ピエルカルロ（2000）「一般競争均衡」『20世紀の主流数理経済学』シュプリンガー、pp.  197– 215、doi : 10.1007/978-3-662-04238-0_16、ISBN 978-3-642-08638-0
• Nilsen, Erlend B.; Pedersen, Simen; Linnell, John DC (2008)「最小凸多角形行動圏は生物学的に意味のある結論を導くために使用できるか？」Ecological Research、23 (3): 635– 639、Bibcode : 2008EcoR...23..635N、doi : 10.1007/s11284-007-0421-9、S2CID  30843551
• オーバーマン、アダム・M.（2007）「凸包は非線形障害問題の解である」アメリカ数学会誌、135（6）：1689–1694、doi：10.1090/S0002-9939-07-08887-9、MR  2286077
• Okon, T. (2000)、「計量空間における Choquet 理論」、Zeitschrift für Analysis und ihre Anwendungen、19 (2): 303–314、doi : 10.4171/ZAA/952、MR  1768994
• オットマン, T.; ソイザロン＝ソイニネン, E.;ウッド, デリック(1984)「直線凸包の定義と計算について」情報科学, 33 (3): 157– 171, doi : 10.1016/0020-0255(84)90025-2
• Prasolov, Victor V. (2004)、「1.2.1 ガウス・ルーカスの定理」、多項式、数学におけるアルゴリズムと計算、第11巻、Springer、pp.  12– 13、doi : 10.1007/978-3-642-03980-5、ISBN 3-540-40714-6、MR  2082772
• Pulleyblank, WR (1983), 「多面体組合せ論」, Bachem, Achim; Korte, Bernhard; Grötschel, Martin (編), Mathematical Programming: The State of the Art (XIth International Symposium on Mathematical Programming, Bonn 1982) , Springer, pp.  312– 345, doi : 10.1007/978-3-642-68874-4_13 , ISBN 978-3-642-68876-8
• ラポポート、アリ（1992）、「単純多角形の凸差分木を構築するための効率的な適応アルゴリズム」、コンピュータグラフィックスフォーラム、11（4）：235– 240、doi：10.1111/1467-8659.1140235、S2CID  20137707
• Reay, John R. (1979)、「Tverbergの定理のいくつかの一般化」、Israel Journal of Mathematics、34 (3): 238–244 (1980)、doi : 10.1007/BF02760885、MR  0570883、S2CID  121352925
• リーフェル、エレノア・G. ; ポラック、ヴォルフガング・H. (2011) 『量子コンピューティング：やさしい入門』 MITプレス、 215～ 216頁 、ISBN 978-0-262-01506-6
• Rockafellar, R. Tyrrell (1970), Convex Analysis , Princeton Mathematical Series, vol. 28, Princeton, NJ: Princeton University Press, MR  0274683
• ロッシ、ヒューゴ（1961）、「複素変数を含む正則凸集合」、数学年報、第2集、74（3）：470-493、doi：10.2307/1970292、JSTOR  1970292、MR  0133479
• Rousseeuw, Peter J. ; Ruts, Ida; Tukey, John W. (1999)「バグプロット：二変量ボックスプロット」アメリカ統計学者、53 (4): 382– 387, doi : 10.1080/00031305.1999.10474494
• 佐久間逸夫（1977）「凸包の閉包性」経済理論誌、14（1）：223-227、doi：10.1016/0022-0531（77）90095-3
• シュナイダー、ロルフ（1993）、凸体：ブルン・ミンコフスキー理論、数学とその応用百科事典、第44巻、ケンブリッジ：ケンブリッジ大学出版局、doi：10.1017/CBO9780511526282、ISBN 0-521-35220-7、MR  1216521
• シートン、キャサリン A. (2017)、「スフェリコンとDフォーム：かぎ針編みのつながり」、数学と芸術ジャーナル、11 (4): 187– 202、arXiv : 1603.08409、doi : 10.1080/17513472.2017.1318512、MR  3765242、S2CID  84179479
• Sedykh、VD (1981)、「空間曲線の凸包の構造」、Trudy seminara imeni IG Petrovskogo (6): 239–256、MR  0630708、ソビエト数学ジャーナル33（4）：1140–1153、1986年、doi：10.1007/BF01086114に翻訳
• ソンタグ, エドゥアルド・D. (1982)、「区分線形代数に関する考察」、パシフィック・ジャーナル・オブ・マスマティクス、98 (1): 183– 201、doi : 10.2140/pjm.1982.98.183、MR  0644949、S2CID  18446330
• Steinitz, E. (1914)、「Bedingt konvergente Reihen und konvexe Systeme. (Fortsetzung)」、Journal für die Reine und Angewandte Mathematik、1914 (144): 1–40、doi : 10.1515/crll.1914.144.1、MR  1580890、S2CID  122998337
• タルマン, ルイス A. (1977), 「​​凸構造を持つ距離空間における多関数の凝縮のための不動点」 ,神大数学セミナー報告, 29 ( 1–2 ): 62– 70, MR  0463985
• トゥーサン、ゴッドフリード（1983）、「回転キャリパーによる幾何学問題の解決」IEEE MELECON '83議事録、アテネ、CiteSeerX  10.1.1.155.5671
• Toussaint, Godfried (1986)、「多角形内の点集合の相対凸包を計算するための最適アルゴリズム」、EURASIPの議事録、信号処理III：理論と応用、第2部、North-Holland、pp.  853– 856
• Weeks, Jeffrey R. (1993)、「尖頭双曲型3次元多様体の凸包と等長変換」、トポロジーとその応用、52 (2): 127– 149、doi : 10.1016/0166-8641(93)90032-9、MR  1241189
• Westermann、LRJ (1976)、「船体オペレーターについて」、Indagationes Mathematicae、38 (2): 179–184、doi : 10.1016/1385-7258(76)90065-2、MR  0404097
• ホワイト、F. ピューリヤー（1923年4月）「純粋数学」、20世紀の科学の進歩、17（68）：517-526、JSTOR  43432008
• Whitley, Robert (1986)、「Kreĭn-Šmulianの定理」、アメリカ数学会誌、97 (2): 376– 377、doi : 10.2307/2046536、JSTOR  2046536、MR  0835903
• Williams, Jason; Rossignac, Jarek (2005)、「Tightening: curvature-limiting morphological simplification」、Kobbelt, Leif; Shapiro, Vadim (eds.)、Proceedings of the Tenth ACM Symposium on Solid and Physical Modeling 2005、マサチューセッツ州ケンブリッジ、米国、2005年6月13日～15日、ACM、pp.  107– 112、doi : 10.1145/1060244.1060257、hdl : 1853/3736、S2CID  15514388
• ワートン、ブルース・J.（1995）「凸包に基づく行動圏サイズの推定量」バイオメトリクス、51（4）：1206–1215、doi：10.2307/2533254、JSTOR  2533254

外部リンク

• 「凸包」、数学百科事典、EMSプレス、2001 [1994]
• ワイスタイン、エリック W.、「凸包」、MathWorld
• 「凸包」、Eric W. Weisstein著、Wolfram Demonstrations Project、2007 年。