ラドンの定理

幾何学 において、 1921 年にヨハン ラドンが発表した凸集合に関するラドンの定理は、次のように述べています。

R ^d内の任意の d + 2 点の集合は、凸包が交差する2 つの集合に分割できます。

これらの凸包の交差点にある点は、その集合のラドン点と呼ばれます。

たとえば、 d = 2の場合、ユークリッド平面 上の 4 つの点の集合は、2 つの方法のいずれかで分割できます。3 点と 1 点 (3 点の凸包 (三角形) に 1 点が含まれる) を形成するか、または交差する 2 つの線分の端点を形成する 2 組の点を形成する場合があります。

d次元空間の任意のd  + 2点の集合を考える。すると、すべてがゼロではない乗数の集合a ₁ , ...,  a _{d  + 2が存在し、}線形方程式系を解く。${\displaystyle X=\{x_{1},x_{2},\dots ,x_{d+2}\}\subset \mathbf {R} ^{d}}$

${\displaystyle \sum _{i=1}^{d+2}a_{i}x_{i}=0,\quad \sum _{i=1}^{d+2}a_{i}=0,}$

 なぜなら、未知数（乗数）はd + 2 個あるが 、それらが満たさなければならない方程式はd + 1 個だけだからです（点の座標ごとに 1 つずつ、乗数の合計が 0 になる最終方程式も 1 つ）。ある特定の非ゼロ解a ₁、...、  a _{d  + 2}を固定します。を正の乗数を持つ点の集合とし、 を負または 0 の乗数を持つ点の集合とします。次に、交差する凸包を持つ 2 つの部分集合に点を分割します。 ${\displaystyle I\subseteq X}$${\displaystyle J=X\setminus I}$${\displaystyle I}$${\displaystyle J}$

との凸包は交差するはずである。なぜなら、どちらも点 ${\displaystyle I}$${\displaystyle J}$

${\displaystyle p=\sum _{x_{i}\in I}{\frac {a_{i}}{A}}x_{i}=\sum _{x_{j}\in J}{\frac {-a_{j}}{A}}x_{j},}$

どこ

${\displaystyle A=\sum _{x_{i}\in I}a_{i}=-\sum _{x_{j}\in J}a_{j}.}$

の式の左辺はこの点を内の点の凸結合として表し、右辺は 内の点の凸結合として表します。したがって、は両方の凸包に属し、証明が完了します。 ${\displaystyle p}$${\displaystyle I}$${\displaystyle J}$${\displaystyle p}$

この証明方法は、ガウス消去法やその他の効率的なアルゴリズムを使用して乗数の連立方程式を解くことで、次元の多項式の時間でラドン点を効率的に構築することを可能にします。 ^[1]

ラドンの定理の同等の定式化は次のようになります。

ƒ が( d  + 1) 次元単体Δ ^d+1からR ^dへの任意のアフィン関数である場合、ƒ による像が交差するΔ ^{d+1の互いに交わらない面が 2 つ存在します。}

これらは同値です。なぜなら、単体上の任意のアフィン関数はその頂点の像によって一意に決まるからです。正式には、 ƒ をΔ ^d+1からR ^dへのアフィン関数とします。を Δ ^d+1の頂点とし、 をƒによるそれらの像とします。元の定式化により、 は、重なり合う凸包を持つ2 つの互いに素な部分集合、たとえば I の ( x _i ) _iと J の ( x _j ) _{jに分割できます。} fはアフィンなので、 I の ( x _i ) _iの凸包は、 I の頂点 ( v _i ) _{iが張る面の像であり、同様にJの (} x _j )jの凸包は、 _{j の頂点 (} v _j )jが張る面の像です。これら 2 つの面は互いに素であり、fによるそれらの像は、新しい定式化で主張されているように交差します。位相的ラドン定理はこの定式化を一般化する。これはfが任意の連続関数（必ずしもアフィン関数ではない）であることを許容する：^[2]${\displaystyle v_{1},v_{2},\dots ,v_{d+2}}$${\displaystyle x_{1},x_{2},\dots ,x_{d+2}}$${\displaystyle x_{1},x_{2},\dots ,x_{d+2}}$

ƒ が( d  + 1) 次元単体Δ ^d+1からR ^dへの任意の連続関数である場合、ƒ による像が交差するΔ ^{d+1の互いに交わらない面が 2 つ存在します。}

より一般的には、K が任意の ( d  + 1) 次元コンパクト凸集合であり、ƒ がKからd次元空間への任意の連続関数である場合、 g が最大値を達成する点とgが最小値を達成する他の点が、 ƒ によって同じ点にマッピングされるような線型関数gが存在する。Kが単体の場合、 gの最大点と最小点によって形成される 2 つの単体面は、像が空でない交差を持つ 2 つの互いに交わらない面でなければならない。この同じ一般的なステートメントを単体ではなく超球に適用すると、 ƒ は球の 2 つの反対の点を同じ点にマッピングしなければならないというBorsuk-Ulam 定理が得られる。 ^[2]

位相的ラドン定理はもともとエルヴィン・バイモチとイムレ・バラニ^[2]によって次のように証明されました。

• (次元球面)から への連続写像を構築します。このとき、球面上のすべての点に対して、およびは の 2 つの互いに交わらない面上にあります。${\displaystyle g}$${\displaystyle S^{d}}$${\displaystyle d}$${\displaystyle \Delta ^{d+1}}$${\displaystyle x}$${\displaystyle g(x)}$${\displaystyle g(-x)}$${\displaystyle \Delta ^{d+1}}$
• ボルスク・ウラム定理を関数 に適用します。これはからまでの連続関数です。定理によれば、任意のそのような関数に対して、となる点が上に存在することになります。${\displaystyle f\circ g}$${\displaystyle S^{d}}$${\displaystyle \mathbb {R} ^{d}}$${\displaystyle y}$${\displaystyle S^{d}}$${\displaystyle f(g(y))=f(g(-y))}$
• 点および はの 2 つの互いに交わらない面上にあり、 によっての同じ点に写像されます。これは、これら 2 つの互いに交わらない面の像が交差することを意味します。${\displaystyle g(y)}$${\displaystyle g(-y)}$${\displaystyle \Delta ^{d+1}}$${\displaystyle f}$${\displaystyle \mathbb {R} ^{d}}$

別の証明は、 László LovászとAlexander Schrijverによって行われました。^[3] 3 番目の証明はJiří Matoušekによって与えられました: ^{[4] : 115}

• を単体とし、を と自身との削除された結合とします。${\displaystyle K}$${\displaystyle \Delta ^{d+1}}$${\displaystyle K_{\Delta }^{*2}}$${\displaystyle K}$
• の幾何学的実現は 球面 に同相であるため、 の Z2 指数は に等しくなります。${\displaystyle K_{\Delta }^{*2}}$${\displaystyle S^{d+1}}$${\displaystyle K_{\Delta }^{*2}}$${\displaystyle d+1}$
• 位相的ラドン定理は、次のより一般的な定理から導かれます。任意の単体複体 に対して、 の Z ₂指数がより大きい場合、から へのすべての連続写像に対して、 の 2 つの互いに交わらない面の像は交差します。${\displaystyle K}$${\displaystyle K_{\Delta }^{*2}}$${\displaystyle d}$${\displaystyle \|K\|}$${\displaystyle \mathbb {R} ^{d}}$${\displaystyle K}$

平面上の任意の4点のラドン点はそれらの幾何中線であり、他の点までの距離の合計が最小となる点である。^{[5] [6]}

ラドンの定理は、凸集合の交差に関するヘリーの定理の標準的な証明の重要なステップを形成します。 ^[7]この証明は、ラドンがラドンの定理を最初に発見した動機でした。

ラドンの定理は、線形分離に関するd次元点のVC 次元を計算するためにも使用できます。 d  + 1 点の集合 (たとえば、正単体の点) が存在し、すべての 2 つの空でない部分集合は超平面によって互いに分離できます。ただし、d  + 2 点のどの集合が与えられても、ラドン分割の 2 つの部分集合は線形に分離できません。したがって、このシステムの VC 次元は正確にd  + 1です^。[8]

d + 2点のセットをラドン点に繰り返し置き換えるランダム化アルゴリズムを使用すると、点の数と次元の両方で多項式の時間で、任意の点セットの中心点の近似値 を計算できます。 ^[1]

幾何中央値。1 次元空間内の 3 つの点のラドン点は、それらの中央値に相当します。点の集合の幾何中央値は、集合内の点までの距離の合計を最小にする点です。これは 1 次元中央値を一般化したもので、施設の位置とロバスト統計の両方の観点から研究されてきました。平面上の 4 つの点の集合の場合、幾何中央値はラドン点と一致します。

トヴェルグの定理。r集合への分割の一般化は、ヘルゲ・トヴェルグ (1966)によって示され、現在ではトヴェルグの定理として知られています。これは、ユークリッドd空間内の任意の点の集合に対して、凸包が少なくとも 1 つの共通点で交差するr個の部分集合への分割が存在することを述べています。 ${\displaystyle (d+1)(r-1)+1\ }$

カラテオドリの定理は、ある点の集合の凸包内の任意の点は、最大でd  + 1 個の点のサブセットの凸包内にも含まれる、つまり、与えられた点は、それが単独であるラドン分割の一部である、ということを述べています。カラテオドリの定理の証明の 1 つは、ラドンの定理の証明に似た、線形方程式のシステムの解を調べる手法を使用して、最大でd  + 1 個になるまで一度に 1 つの点を削除します。

凸幾何学。ラドンの定理に関連する概念は、凸幾何学、つまり、族内の任意の 2 つの集合の交差は族内に残り、空集合とすべての集合の和集合は族に属するという性質を持つ有限集合の族に対しても考慮されてきた。このより一般的な文脈では、集合Sの凸包はS を含む族のメンバーの交差であり、空間のラドン数は、任意のr点が凸包が交差する 2 つの部分集合を持つ最小のrである。同様に、ユークリッド空間の凸集合に対する定義から類推して、ヘリー数hとカラテオドリ数c を定義することができ、これらの数が不等式h  <  r  ≤  ch  + 1を満たすことが示される。^[9]

グラフのラドン定理。任意の無向グラフにおいて、頂点の組を結ぶ誘導 経路をすべて含む頂点の集合を凸集合と定義することができる。この定義によれば、グラフ内のω + 1個の頂点の集合はすべて、凸包が交差する2つの部分集合に分割することができ、ω + 1はこれが可能な最小の数である。ここでωは与えられたグラフのクリーク数である。 ^{[10]誘導経路の代わりに}最短経路を含む関連結果については、Chepoi (1986)およびBandelt & Pesch (1989)を参照のこと。

• バジモチ、EG; Bárány, I. (1979)、「ボルスクとラドンの定理の共通一般化」、Acta Mathematica Hungarica、34 (3–4): 347–350、doi :10.1007/BF01896131、S2CID  12971298。
• バンデルト、H.-J. Pesch, E. (1989)、「ヘリー グラフのラドン定理」、Archiv der Mathematik、52 (1): 95–98、doi :10.1007/BF01197978、S2CID  120983560。
• Chepoi, VD (1986)、「三角形グラフの d 凸性のいくつかの特性」、Mat. Issled. (ロシア語)、87 : 164–177。 Bandelt & Pesch (1989) によって引用されています。
• クラークソン、ケネス L. ;エップスタイン、デビッド;ミラー、ゲイリー L. ; スターティバント、カール ;テン、シャン・フア(1996)、「反復ラドン ポイントによる中心点の近似」、International Journal of Computational Geometry & Applications、6 (3): 357–377、doi :10.1142/s021819599600023x、MR  1409651。
• Danzer, L.; Grünbaum, B .; Klee, V. (1963)、「Helly の定理とその類似物」、Convexity、Proc. Symp. Pure Math.、vol. 7、American Mathematical Society、pp. 101–179。
• デュシェ、ピエール（1987）「グラフの凸集合。II. 最小経路凸性」、組合せ理論ジャーナル、シリーズA、44（3）：307–316、doi：10.1016/0095-8956（88）90039-1。 Bandelt & Pesch (1989) によって引用されています。
• エックホフ、J. (1993)、「ヘリー、ラドン、カラテオドリ型定理」、凸幾何学ハンドブック、第 A 巻、第 B 巻、アムステルダム: 北ホラント、pp. 389–448。
• ケイ、デイビッド C.; ウォンブル、ユージン W. (1971)、「公理的凸性理論とカラテオドリ数、ヘリー数、ラドン数の関係」、パシフィック ジャーナル オブ マスマティクス、38 (2): 471–485、doi : 10.2140/pjm.1971.38.471、MR  0310766。
• Matoušek, J. (2002)、「1.3 ラドンの補題とヘリーの定理」、離散幾何学講義、数学大学院テキスト、第212巻、Springer-Verlag、pp. 9-12、ISBN 978-0-387-95373-1。
• Matoušek, J. (2003)、「5.1 非埋め込み性定理: 入門」、Borsuk–Ulam 定理の使用: 組合せ論と幾何学における位相的手法の講義、Springer-Verlag、pp. 88–92。
• Radon, J. (1921)、「Mengen konvexer Körper, die einen gemeinsamen Punkt enthalten」、Mathematische Annalen、83 (1–2): 113–115、doi :10.1007/BF01464231、S2CID  121627696。
• Tverberg, H. (1966)、「ラドンの定理の一般化」、ロンドン数学会誌、41 : 123–128、doi :10.1112/jlms/s1-41.1.123。