라돈의 정리

1921년 요한 라돈이 발표한 볼록 집합에 관한 라돈의 정리는 기하학에서 다음과 같이 기술하고 있습니다.

R의^d 임의의 d + 2 점 집합은 볼록 껍질이 교차하는 두 집합으로 분할할 수 있습니다.

이 볼록한 선체들의 교점에 있는 한 점을 집합의 라돈 점이라고 합니다.

예를 들어, 대소문자 d = 2의 경우, 유클리드 평면의 임의의 4개 점 집합은 두 가지 방법 중 하나로 분할될 수 있습니다. 트리플과 싱글톤을 형성할 수 있으며, 트리플(삼각형)의 볼록한 선체에는 싱글톤이 포함되어 있습니다. 또는 교차하는 두 선분의 끝점을 형성하는 두 쌍의 점을 형성할 수 있습니다.

증명 및 구축

임의의 집합 $X$ =${\displaystyle }${ x $,$ $x$ 2, …, x d + 2 } ⊂ R {\displaystyle X=\{x_{1}, x_{2},\dots,x_{d+2}\}\subset \mathbf {R}^{d}를 d차원 공간에 있는 점으로 생각하자. 그렇다면 선형 방정식 체계를 푸는 곱셈₁ a, ..., a의_{d + 2} 집합은 모두 0이 아닙니다.

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

d + 2개의 미지수(승수)가 있지만 이들이 만족해야 하는 방정식은 d + 1개뿐이기 때문입니다(승수의 합이 0이어야 하는 최종 방정식과 함께 점의 각 좌표에 대해 하나). 0이 아닌 특정 해 a, ..., a를 고칩니다. $X$ {\$displaystyle I\subseteq$ X}를 양의 승수를 갖는 점들의 집합으로 ⊆$하고$,$$ =$$X ∖ I {\$displaystyle J$=X\setminus I}를 음 또는 0의 승수를 갖는 점들의 집합으로 합니다. 그런 다음 $I{\displaystyle }$ ${\displaystyle I}$ 및$$ $J{\displaystyle }$ ${\displaystyle J}$는 점의 필요한 파티션을 볼록한 선체가 교차하는 두 부분집합으로 구성합니다$$.

$I{\displaystyle }$ ${\displaystyle I}$ 및$$ $J{\displaystyle }$ ${\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}.}$

$p{\displaystyle }$ ${\displaystyle p}$에 대한 공식의 왼쪽은 이 $점$을$$I {\$displaystyle I$$}$의 점들의 볼록한 조합으로$$표현하고$$ $오른쪽$은$$J {\$displaystyle$ J}의 점들의 볼록한 조합으로 표현합니다$.$ $따라서{\displaystyle }$p {\$displaystyle$ p$}$는 양쪽 볼록한 선체에 속합니다$$. 증명을 완료하는 중입니다.

이 증명 방법은 가우스 제거 또는 기타 효율적인 알고리즘을 사용하여 승수에 대한 방정식 시스템을 해결함으로써 차원에서 다항식인 시간 내에 라돈 점을 효율적으로 구성할 수 있습니다.^[1]

위상 라돈 정리

라돈의 정리와 동등한 공식은 다음과 같습니다.

ƒ가 (d + 1)차원 단순 δ에서 R까지의 아핀 함수인 경우, ƒ 아래의 영상이 교차하는 δ의 두 개의 분리된 면이 있습니다.

이들은 심플렉스의 모든 아핀 함수가 정점의 이미지에 의해 고유하게 결정되기 때문에 동등합니다. 형식적으로, ƒ를 δ에서 R까지의 아핀 함수라고 합니다. $v$ ${\displaystyle 1_{}}$ ${\displaystyle {}_{}}$ ${\displaystyle 2_{}\dots ,}$ ${\displaystyle v_{}}$ ${\displaystyle {\mathrm{d}}_{}}$+ 2 ${\displaystyle v_{1}, v_{2},\dots,v_{d+2}}$를 δ의 정점으로 ${\displaystyle {하고}_{}}$ x${\displaystyle {}_{}}$1${\displaystyle ,{}_{}}$ ${\displaystyle 2_{}}$,${\displaystyle {}_{}}$…, ${\displaystyle {\mathrm{x}}_{}}$d + 2 {\$displaystyle x_{$1}, $x_${2$},\dots,$x_{d+2}}를${\displaystyle {}_{}}$ƒ의 이미지로 지정합니다. $원래{\displaystyle {}_{}}$ 공식에 의해 x ${\displaystyle {1\mathrm{}}_{}}$ ${\displaystyle {x\mathrm{}}_{}}$ ${\displaystyle {}_{}\dots ,}$ ${\displaystyle x_{}}$ ${\displaystyle {\mathrm{d}}_{}}$+ 2 ${\$는 두 개의 서로 다른 부분집합, 예를 들어 (x_i)_{i in I}와 (x_j)_{j in J,}가 겹친 볼록한 선체로 분할될 수 있습니다$$. f가 아핀이므로 (x_i)_{i in I}의 볼록한 선체는 정점(v_i)에 의해 스패닝된 면의 이미지이고,_{i in I} 마찬가지로 (x_j)j의 볼록한 선체는 정점(v_j)j에 의해 스패닝된 면의 이미지입니다. 이 두 개의 면은 서로 분리되어 있으며 f 아래의 이미지는 새로운 공식에 의해 주장된 바와 같이 교차합니다. 위상적 라돈 정리는 이 공식을 일반화합니다. f는 어떤 연속적인 기능일 수 있습니다. 반드시 아핀일 필요는 없습니다.^[2]

ƒ이 (d + 1)차원 단순 δ에서 R까지의 연속 함수인 경우, ƒ 아래의 영상이 교차하는 두 개의 분리된 δ 면이 있습니다.

보다 일반적으로, K가 임의의 (d + 1)차원 콤팩트 볼록 집합이고, ƒ가 K에서 d차원 공간까지의 임의의 연속 함수이면, g가 최댓값을 달성하는 점과 g가 최솟값을 달성하는 점이 동일한 점에 ƒ로 매핑되는 선형 함수 g가 존재합니다. K가 심플렉스인 경우, g의 최대점과 최소점에 의해 형성되는 두 심플렉스 면은 이미지가 비어 있지 않은 교차점을 갖는 두 개의 서로소 면이어야 합니다. 이와 같은 일반적인 설명은, 단순한 표현 대신 초구에 적용될 때, 보르숙-울람 정리, 그 ƒ는 구면의 두 개의 반대점을 같은 점에 매핑해야 합니다.

증명

위상적 라돈 정리는 원래 다음과 같은 방법으로 Bajmoczy와 Barany에^[2] 의해 증명되었습니다.

• 구면의 모든 점 x에 대하여 g(x)와 g(-x)가 δ δ의 서로소인 두 면에 있도록 S(d차원 구면)에서 δ까지 연속적인 지도 g를 작성합니다.
• 보르숙을 바릅니다.함수 ${\displaystyle f}$에 대한 울람 정리는 S에서 R까지의 연속 함수인 ∘ g${\displaystyle$f$\backslash$circ}이다. 이 정리는 임의의 그러한 함수에 대하여, S 위에 f(g(y) = f(g (-리)와 같은 점 y가 존재한다고 말합니다.
• 점 g(y) 및 g(-y)는 δ δ의 두 개의 서로소 면에 있으며, 점 f는 R의 동일한 점에 매핑됩니다. 이것은 이 두 개의 분리된 면의 이미지가 교차한다는 것을 의미합니다.

또 다른 증거는 Lovasz와 Schrijver에 의해 제시되었습니다.^[3] 마투섹은 세 번째 증거를 제시합니다.^{[4]: 115}

• K를 심플렉스 δ라고 ${\displaystyle {하고}_{}^{}}$ K δ$$∗ 2 ${\displaystyle$ K_{\Delta }^{*2}}를 K의 삭제된 결합으로${\displaystyle {\mathrm{합니다}}_{}^{}}$.
• $K$δ ∗ 2 ${\displaystyle$K_{\Delta }^{*2}}의 기하학적 구현은 구 S와 동형입니다.
• $따라서$ K$$δ ∗ 2${\displaystyle$K_{\Delta }^{*2}}의 Z-index는 d+1과 같습니다.
• 위상적 라돈 정리는 다음과 같은 보다 일반적인 정리로부터 이어집니다. 임의의 단순한 복소 K의 경우, $K$δ ∗ 2 ${\display$K_{\Delta}^{*2}의 Z-index가 d보다 크다면, K에서 R로 연속적으로 매핑될 때마다 K의 서로소인 두 면의 영상이 교차합니다.

적용들

평면에 있는 모든 네 점의 라돈 점은 다른 점까지의 거리의 합을 최소화하는 점인 기하학적 중앙값입니다.^[5][6]

라돈의 정리는 볼록 집합의 교차점에 대한 헬리 정리의 표준 증명의 핵심 단계를 형성합니다.^[7] 이 증명은 라돈의 정리를 최초로 발견하게 된 동기가 되었습니다.

라돈의 정리는 선형 분리에 대한 d차원 점의 VC 차원을 계산하는 데에도 사용할 수 있습니다. 모든 두 개의 비어 있지 않은 부분집합을 초평면으로 분리할 수 있도록 d + 1개의 점(예를 들어, 정규 심플렉스의 점)의 집합이 존재합니다. 그러나 어떤 집합의 d + 2 점이 주어지더라도 라돈 파티션의 두 부분 집합은 선형으로 분리될 수 없습니다. 따라서 이 시스템의 VC 차원은 정확히 d + 1입니다.^[8]

d + 2개의 점 집합을 반복적으로 라돈 점으로 대체하는 무작위 알고리즘을 사용하여 점 수와 차원 모두에서 다항식인 시간 내에 모든 점 집합의 중심점에 대한 근사치를 계산할 수 있습니다.^[1]

관련개념

기하 중앙값. 1차원 공간에 있는 세 점의 라돈 점은 그들의 중앙값에 불과합니다. 점 집합의 기하학적 중앙값은 집합의 점까지의 거리의 합을 최소화하는 점으로, 1차원 중앙값을 일반화하며 시설 위치와 강건한 통계학의 관점에서 모두 연구되었습니다. 평면에 있는 네 점의 집합의 경우 기하 중앙값이 라돈 점과 일치합니다.

Tverberg의 정리. r개의 집합으로 분할하는 일반화는 Helge Tverberg(1966)에 의해 주어졌으며 현재 Tverberg의 정리로 알려져 있습니다. 유클리드 d-공간의 임의의 집합${\displaystyle }$(${\displaystyle d}$+ ${\displaystyle 1)}$ (${\displaystyle r}$ ${\displaystyle -}$ ${\displaystyle 1)}$ + ${\displaystyle 1}${\$displaystyle (d$+ 1) ($r-1)$ + $1\}$개의$$ 점에 대하여, 볼록한 선체가 적어도 하나의 공통점에서 교차하는 r 부분집합으로 분할이 있다는 것을 말합니다.

카라테오도리 정리는 어떤 점들의 집합의 볼록한 선체에 있는 어떤 점도 최대 d + 1의 점들의 부분 집합의 볼록한 선체 내에 있다는 것을 말합니다. 즉, 주어진 점은 단일 톤인 라돈 파티션의 일부라는 것입니다. 카라테오도리 정리의 한 증명은 라돈 정리의 증명과 유사하게 선형 방정식 체계에 대한 해를 조사하는 기술을 사용하여 기껏해야 d + 1이 남을 때까지 한 번에 한 점을 제거합니다.

볼록 기하학. 라돈의 정리와 관련된 개념은 볼록 기하학, 가군의 임의의 두 집합의 교집합이 가군에 남아 있고 빈 집합과 모든 집합의 합이 가군에 속한다는 성질을 가진 유한 집합의 가군에 대해서도 고려되었습니다. 보다 일반적인 맥락에서 집합 S의 볼록한 선체는 S를 포함하는 가족 구성원들의 교집합이고, 공간의 라돈 수는 r개의 점이 볼록한 선체가 교차하는 두 부분집합을 가질 수 있도록 가장 작습니다. 마찬가지로, 유클리드 공간에서 볼록 집합에 대한 정의와 유사하게 헬리 수 h와 카라테오도리 수 c를 정의할 수 있으며, 이 수들은 부등식 h < r ≤ ch + 1을 만족한다는 것을 보여줄 수 있습니다.^[9]

그래프에 대한 라돈 정리. 임의의 무방향 그래프에서, 볼록 집합을 집합 내의 정점 쌍을 연결하는 모든 유도 경로를 포함하는 정점 집합으로 정의할 수 있습니다. 이 정의를 사용하면 그래프의 모든 ω + 1 꼭짓점 집합을 볼록한 선체가 교차하는 두 부분 집합으로 분할할 수 있으며, ω + 1은 이를 수행할 수 있는 최소 개수이며, 여기서 ω는 주어진 그래프의 클리크 개수입니다. 유도 경로 대신 최단 경로를 포함하는 관련 결과는 Chepoi(1986)와 Bandelt & Pesch(1989)를 참조하십시오.

메모들

참고문헌

• Bajmóczy, E. G.; Bárány, I. (1979), "A common generalization of Borsuk's and Radon's theorem", Acta Mathematica Hungarica, 34 (3–4): 347–350, doi:10.1007/BF01896131, S2CID 12971298.
• Bandelt, H.-J.; Pesch, E. (1989), "A Radon theorem for Helly graphs", Archiv der Mathematik, 52 (1): 95–98, doi:10.1007/BF01197978, S2CID 120983560.
• Chepoi, V. D. (1986), "Some properties of the d-convexity in triangulated graphs", Mat. Issled. (in Russian), 87: 164–177Bandelt & Pesch(1989)가 인용한 Chepoi, V. D. (1986), "Some properties of the d-convexity in triangulated graphs", Mat. Issled. (in Russian), 87: 164–177바와 같이.
• Clarkson, Kenneth L.; Eppstein, David; Miller, Gary L.; Sturtivant, Carl; Teng, Shang-Hua (1996), "Approximating center points with iterated Radon points", 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's theorem and its relatives", Convexity, Proc. Symp. Pure Math., vol. 7, American Mathematical Society, pp. 101–179.
• Duchet, Pierre (1987), "Convex sets in graphs. II. Minimal path convexity", Journal of Combinatorial Theory, Series A, 44 (3): 307–316, doi:10.1016/0095-8956(88)90039-1Bandelt & Pesch(1989)가 인용한 Duchet, Pierre (1987), "Convex sets in graphs. II. Minimal path convexity", Journal of Combinatorial Theory, Series A, 44 (3): 307–316, doi:10.1016/0095-8956(88)90039-1바와 같이.
• Eckhoff, J. (1993), "Helly, Radon, and Carathéodory type theorems", Handbook of Convex Geometry, vol. A, B, Amsterdam: North-Holland, pp. 389–448.
• Kay, David C.; Womble, Eugene W. (1971), "Axiomatic convexity theory and relationships between the Carathéodory, Helly, and Radon numbers", Pacific Journal of Mathematics, 38 (2): 471–485, doi:10.2140/pjm.1971.38.471, MR 0310766.
• Matoušek, J. (2002), "1.3 Radon's Lemma and Helly's Theorem", Lectures on Discrete Geometry, Graduate Texts in Mathematics, vol. 212, Springer-Verlag, pp. 9–12, ISBN 978-0-387-95373-1.
• Matoušek, J. (2003), "5.1 Nonembeddability Theorems: An Introduction", Using the Borsuk–Ulam Theorem: Lectures on Topological Methods in Combinatorics and Geometry, 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), "A generalization of Radon's theorem" (PDF), Journal of the London Mathematical Society, 41: 123–128, doi:10.1112/jlms/s1-41.1.123^{[dead link]}.