라돈의 정리

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요
2. 정의와 증명
- 2.1. 선형 방정식 시스템을 이용한 증명
- 2.2. 위상수학적 증명
3. 관련 개념
4. 응용
참조

1. 개요

라돈의 정리는 d차원 공간에서 d+2개의 점 집합을 두 개의 부분 집합으로 분할할 수 있으며, 각 부분 집합의 볼록 껍질이 교차한다는 기하학적 정리이다. 이 정리는 선형 방정식 시스템을 이용하거나 위상수학적 방법으로 증명할 수 있으며, 헬리의 정리, 트베르그 정리, 카라테오도리 정리 등과 관련이 있다. 라돈의 정리는 기하학적 중심, VC 차원 계산, 무작위 알고리즘을 이용한 중간점 근사 등 다양한 분야에 응용된다.

더 읽어볼만한 페이지

볼록 껍질 - 볼록 조합
볼록 조합은 실수 벡터 공간에서 유한 개의 점들을 0 이상의 계수 합이 1이 되도록 선형 결합한 것으로, 볼록 집합과 볼록 껍질의 정의에 사용되며 확률 분포 혼합, 모델 앙상블, 경제 모델링 등에 활용된다.
볼록 껍질 - 크레인-밀만 정리
크레인-밀만 정리는 함수 해석학에서 콤팩트 볼록 집합이 극점을 가지며, 하우스도르프 국소 볼록 공간에서 극점의 닫힌 볼록 폐포와 같다는 것을 보이는 정리로, 마르크 크레인과 다비드 밀만에 의해 증명되었다.
볼록기하학 정리 - 브라우어르 고정점 정리
브라우어르 고정점 정리는 콤팩트 볼록 집합에서 자기 자신으로 가는 연속 함수는 반드시 고정점을 가진다는 정리로, 다양한 공간에서 여러 형태로 표현되며 함수해석학에서 중요한 역할을 한다.
볼록기하학 정리 - 헬리의 정리
헬리의 정리는 d차원 공간의 볼록 부분집합들 중 임의의 d+1개의 교집합이 공집합이 아니면 전체 집합의 교집합도 공집합이 아니라는 정리이다.

라돈의 정리
라돈의 정리
분야	기하학
설명	d+2 점을 d차원에서 분리
관련 항목	헬리의 정리

2. 정의와 증명

d^영어차원 공간에서 d^영어 + 2개의 점으로 이루어진 집합을 생각해보자. 라돈 정리에 따르면, 이 집합은 볼록 껍질이 서로 교차하는 두 개의 부분집합으로 나눌 수 있다.

이러한 분할은 연립 일차 방정식을 풀어 얻을 수 있으며, 가우스 소거법과 같은 효율적인 알고리즘을 통해 다항 시간 안에 라돈 점을 계산할 수 있다.^[1]

라돈 정리는 다음과 같이 표현될 수도 있다.

> (d + 1)차원 단순체에서 '''실수'''^d로의 임의의 아핀 함수 ƒ가 주어졌을 때, ƒ에 의해 이미지들이 교차하는 Δ^d+1의 두 개의 서로소인 면이 존재한다.

이는 단순체 상의 모든 아핀 함수가 꼭짓점의 이미지에 의해 고유하게 결정되기 때문에 원래의 라돈 정리와 동등하다.
위상 라돈 정리는 이 공식을 일반화하여, ƒ가 아핀 함수일 필요 없이 임의의 연속 함수가 되도록 허용한다.^[2]

> ƒ가 (d + 1)차원 단순체 Δ^d+1에서 '''실수'''^d로의 임의의 연속 함수라면, ƒ에 의해 이미지들이 교차하는 Δ^d+1의 두 개의 서로소인 면이 존재한다.

더 일반적으로, ''K''가 임의의 (''d'' + 1)차원 콤팩트 볼록 집합이고 ƒ가 ''K''에서 ''d''차원 공간으로의 임의의 연속 함수라면, ''g''가 최댓값을 갖는 점과 ''g''가 최솟값을 갖는 다른 점이 ƒ에 의해 동일한 점으로 매핑되는 선형 함수 ''g''가 존재한다. ''K''가 단순체인 경우, ''g''의 최대 및 최소 지점에 의해 형성된 두 개의 단순체 면은 이미지의 교집합이 비어 있지 않은 두 개의 서로소인 면이어야 한다. 이와 동일한 일반적인 명제가 단순체 대신 초구에 적용되면 ƒ가 구의 두 개의 반대점을 동일한 점으로 매핑해야 한다는 보르수크-울람 정리가 나온다.^[2]

2. 1. 선형 방정식 시스템을 이용한 증명

평면에서 네 점을 가지는 두 집합(정사각형의 꼭짓점과 정삼각형과 중심), 이 점들의 세 연립 일차 방정식을 푸는 계수들, 그리고 양의 계수로 이루어진 점과 음의 계수로 이루어진 점으로 분리된 라돈 분할을 나타낸 것이다.

''d''차원 공간에 있는 ''d'' + 2개의 점들로 이루어진 집합

\{x_1,x_2,\dots,x_{d+2}\}\subset \mathbf{R}^d

을 생각해보자. 그러면 다음 연립 일차 방정식을 만족하면서 모두 0은 아닌 계수들의 집합 ''a''₁, ..., ''a''_{''d'' + 2}가 존재한다.

:

\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''_{''d'' + 2}를 고정할 수 있다. ''I''를 양의 계수를 가지는 점들의 집합이라 하고, ''J''를 음 또는 영의 계수를 가지는 점들의 집합이라 하자. 그러면 ''I''와 ''J''는 점들을 두 부분집합으로 나누는데, 이 두 부분집합의 볼록 폐포는 서로 교차한다.

''I''와 ''J''의 볼록 폐포는 다음 점을 공통으로 포함하기 때문에 교차한다.

:

p= \sum_{i\in I}\frac{a_i}{A} x_i=\sum_{j\in J}\frac{-a_j}{A}x_j,

이때,

A

는 다음과 같다.

:

A=\sum_{i\in I} a_i=-\sum_{j\in J} a_j.

위 식의 좌변은 ''p''를 ''I''에 있는 점들의 볼록 조합으로 나타내고, 우변은 ''p''를 ''J''에 있는 점들의 볼록 조합으로 나타낸다. 따라서 ''p''는 양쪽 볼록 폐포 모두에 포함된다.

이 증명 방법은 가우스 소거법이나 연립 일차 방정식을 풀기 위한 다른 효율적인 알고리즘을 사용하여, 다항 시간 안에 라돈 점을 계산할 수 있게 한다.^[1]

2. 2. 위상수학적 증명

라돈의 정리의 위상수학적인 일반화는 다음과 같다. ƒ가 (''d'' + 1)차원 단체에서 ''d''차원 공간까지 연속인 함수일 때, 그 단체는 ƒ의 상에서는 교차하지만 서로 교차하지 않는 두 개의 면을 가진다.^[12] 라돈의 정리 자체는 ƒ가 단체의 꼭짓점을 ''d''차원 공간의 ''d'' + 2개의 점으로 가지는 유일한 아핀 맵인 특수한 경우로 해석될 수 있다.

더 일반적으로, ''K''가 (''d'' + 1)차원 콤팩트 볼록 집합이고, ƒ가 ''K''에서 ''d''차원 공간까지 연속인 함수라고 하면, ''g''가 최댓값을 가지는 점들과 최솟값을 가지는 점들이 ƒ의 같은 점에 매핑되는 선형 함수 ''g''가 존재한다. ''K''가 단체인 경우에, ''g''의 최솟점과 최댓점으로 생성되는 두 단체의 면들은 그러면 반드시 두 교차하지 않는 면들의 상들의 교집합은 공집합이 아니게 된다. 이 일반적인 명제를 단체 대신에 초구에 적용하면 ƒ가 반드시 구의 두 극점에 같은 점에 매핑되는 보르수크-울람 정리를 얻는다.^[12]

위상적 라돈 정리는 ''f''가 반드시 아핀 함수일 필요는 없으며, 임의의 연속 함수가 되도록 허용한다.^[2]

> ƒ가 (''d'' + 1)차원 단순체 Δ^d+1에서 '''실수'''^d로의 임의의 연속 함수라면, ƒ에 의해 이미지들이 교차하는 Δ^d+1의 두 개의 서로소인 면이 존재한다.

이 정리는 임레 바라니에 의해 증명되었는데,^[2] 증명 과정은 다음과 같다.

$S^d$ ( $d$ 차원 초구)에서 $\Delta^{d+1}$ 로의 연속 함수 $g$ 를 구성한다. 여기서 구의 모든 점 $x$ 에 대해, $g(x)$ 와 $g(-x)$ 는 $\Delta^{d+1}$ 의 두 개의 서로소인 면 위에 있다.
함수 $f\circ g$ 에 보르수크-울람 정리를 적용한다. 이는 $S^d$ 에서 $\mathbb{R}^d$ 로의 연속 함수이다. 이 정리에 따르면, 이러한 함수에 대해 $S^d$ 의 어떤 점 $y$ 가 존재하여 $f(g(y)) = f(g(-y))$ 가 성립한다.
점 $g(y)$ 와 $g(-y)$ 는 $\Delta^{d+1}$ 의 두 개의 서로소인 면 위에 있으며, 이들은 $f$ 에 의해 $\mathbb{R}^d$ 의 같은 점으로 매핑된다. 이는 이 두 개의 서로소인 면의 이미지가 서로 교차함을 의미한다.

러슬로 러바스와 알렉산더 슈리이버에 의해 또 다른 증명이 제시되었다.^[3] 이르지 마토우셰크는 세 번째 증명을 제시했다.^[4]

3. 관련 개념

라돈 정리는 기하학적 중앙값, 헬리의 정리, VC 차원, 무작위 알고리즘, 트베르그 정리, 카라테오도리 정리, 볼록 기하, 그래프 이론 등 다양한 분야 및 개념과 관련되어 있다.^[1]^[5]^[6]^[7]^[9]^[10]

3. 1. 기하학적 중앙값

평면에서 어떤 네 점의 라돈 점은 다른 점들과의 거리의 합이 최소인 기하학적 중심이다.^[5]^[6]^[13]^[14]

3. 2. 헬리의 정리

라돈의 정리는 헬리의 정리 증명에서 볼록 집합의 교점에 대한 표준적인 증명의 핵심 단계이다.^[15]^[7] 이 증명은 라돈이 라돈의 정리를 처음 발견하게 된 동기였다.

3. 3. VC 차원

라돈의 정리는 선형 분리 관점에서 ''d''차원 점들의 VC 차원을 계산하는 데 사용된다. 모든 두 공집합이 아닌 부분집합이 서로 초평면으로 분리될 수 있는 ''d'' + 1개의 점 집합(예를 들어, 정단체의 점들)이 존재한다. 하지만 어떤 ''d'' + 2개의 점 집합이 주어지더라도, 라돈 분할의 두 부분집합은 선형적으로 분리될 수 없다. 따라서, 이 계의 VC 차원은 정확히 ''d'' + 1이다.^[16]

3. 4. 트베르그 정리

라돈 정리는 트베르그 정리에 의해 일반화될 수 있다. 트베르그 정리는 유클리드 ''d''-공간의

(d + 1)(r - 1) + 1

개의 점 집합에 대해, 볼록 껍질이 적어도 하나의 공통 점에서 교차하는 ''r''개의 부분 집합으로의 분할이 존재한다고 명시한다.^[9]

3. 5. 카라테오도리 정리

카라테오도리 정리는 점들의 집합의 볼록 껍질 내의 모든 점은 최대 ''d'' + 1개 점의 부분 집합의 볼록 껍질 내에 있다는 것을 명시한다. 즉, 주어진 점은 그것이 단일 원소인 라돈 분할의 일부이다. 카라테오도리 정리의 한 가지 증명은 라돈의 정리의 증명과 유사하게, 선형 방정식 시스템의 해를 검토하는 기술을 사용하여 최대 ''d'' + 1개가 남을 때까지 한 번에 한 점을 제거한다.^[9]

3. 6. 볼록 기하와 그래프에서의 라돈 정리

라돈 정리는 추상적인 볼록 기하 및 그래프 이론에도 적용될 수 있다.

볼록 기하에서, 집합 ''S''의 볼록 껍질은 ''S''를 포함하는 가족 구성원들의 교집합이며, 공간의 라돈 수는 임의의 ''r''개의 점이 볼록 껍질이 교차하는 두 개의 부분 집합을 갖는 가장 작은 ''r''이다. 유사하게, 유클리드 공간의 볼록 집합에 대한 정의와 유사하게 헬리(Helly) 수 ''h''와 카라테오도리(Carathéodory) 수 ''c''를 정의할 수 있으며, 이 숫자들은 부등식 ''h'' < ''r'' ≤ ''ch'' + 1을 만족한다.^[9]

임의의 무방향 그래프에서, 볼록 집합을 집합 내의 점들의 쌍을 연결하는 모든 유도된 경로를 포함하는 정점들의 집합으로 정의할 수 있다. 이 정의를 사용하면, 그래프의 모든 ω + 1개의 정점 집합을 볼록 껍질이 교차하는 두 개의 부분 집합으로 분할할 수 있으며, ω + 1은 이것이 가능한 최소 숫자이다. 여기서 ω는 주어진 그래프의 클리크 수이다.^[10] 유도된 경로 대신 최단 경로를 포함하는 관련된 결과에 대해서는 다른 연구자들의 자료를 참고할 수 있다.

4. 응용

라돈의 정리는 여러 분야에 응용된다.

기하학적 문제: 평면 상의 임의의 네 점에 대한 라돈 점은 다른 점까지의 거리 합을 최소화하는 기하학적 중앙값이다.^[5]^[6]
헬리의 정리 증명: 볼록 집합의 교차점에 대한 헬리의 정리의 표준 증명에 사용되며, 이는 라돈이 자신의 정리를 발견하게 된 동기였다.^[7]
기계 학습: VC 차원을 계산하는 데 사용된다. ''d''차원 점들의 선형 분리 가능성을 판단하는 기준으로, ''d'' + 1개의 점 집합은 초평면에 의해 서로 분리될 수 있지만, ''d'' + 2개의 점 집합은 라돈 분할에 의해 생성된 두 부분집합이 선형적으로 분리될 수 없다. 따라서 VC 차원은 ''d'' + 1이다.^[8]
최적화: ''d'' + 2개의 점 집합을 반복적으로 라돈 점으로 대체하는 무작위 알고리즘을 사용하여, 점의 개수와 차원에 대해 다항식 시간 내에 임의의 점 집합의 중심점에 대한 근사 알고리즘을 계산할 수 있다.^[1]

4. 1. 기하학적 문제

평면 상의 임의의 네 점에 대한 라돈 점은 다른 점까지의 거리 합을 최소화하는 점인 기하학적 중앙값이다.^[5]^[6]

4. 2. 기계 학습

라돈의 정리는 VC 차원을 계산하는 데 사용될 수 있다. 여기서 VC 차원은 d차원 점들의 선형 분리 가능성을 판단하는 기준이 된다. d + 1개의 점 집합은 초평면에 의해 서로 분리될 수 있는 두 개의 비어있는 부분집합으로 나뉠 수 있다(예: 정규 심플렉스의 점). 그러나 d + 2개의 점 집합에서는 라돈 분할에 의해 생성된 두 부분집합이 선형적으로 분리될 수 없다. 따라서 이 시스템의 VC 차원은 정확히 d + 1이다.^[8]

4. 3. 최적화

''d'' + 2개의 점 집합을 반복적으로 라돈 점으로 재배치하는 무작위 알고리즘은 점의 개수와 차원에 관한 다항 시간 안에 모든 점 집합의 중간점을 근사한다.^[11]

4. 4. 기타

라돈의 정리는 헬리의 정리의 볼록 집합의 교점에 대한 표준적인 증명의 핵심 단계로 작용하며,^[15]^[7] 이 증명은 라돈이 라돈의 정리를 처음 발견하게 된 동기였다.

라돈의 정리는 선형 분리를 기준으로 하는 ''d''차원 점들의 VC 차원을 계산하는 데에도 사용될 수 있다. 두 개의 비어있는 부분집합이 초평면에 의해 서로 분리될 수 있는 ''d'' + 1개의 점 집합(예: 정규 심플렉스의 점)이 존재한다. 그러나 어떤 ''d'' + 2개의 점 집합이 주어지든 간에 라돈 분할의 두 부분집합은 선형적으로 분리할 수 없다. 따라서 이 시스템의 VC 차원은 정확히 ''d'' + 1이다.^[16]^[8]

''d'' + 2개의 점 집합을 반복적으로 해당 라돈 점으로 대체하는 무작위 알고리즘을 사용하여, 점의 수와 차원에 대해 다항식 시간 내에 임의의 점 집합의 중심점에 대한 근사 알고리즘을 계산할 수 있다.^[11]^[1]

참조

_[1] harvtxt
_[2] 학술지 On a common generalization of Borsuk's and Radon's theorem https://doi.org/10.1[...] 1979-09-01
_[3] 학술지 A Borsuk theorem for antipodal links and a spectral characterization of linklessly embeddable graphs https://www.ams.org/[...] 1998
_[4] 서적 Using the Borsuk-Ulam Theorem: Lectures on Topological Methods in Combinatorics and Geometry Springer-Verlag 2007
_[5] 서적 Shortest Connectivity: An Introduction with Applications in Phylogeny https://books.google[...] Springer
_[6] 간행물 Four-point Fermat location problems revisited. New proofs and extensions of old results http://mosi.vub.ac.b[...]
_[7] harvtxt
_[8] 웹사이트 Epsilon-nets and VC-dimension https://web.archive.[...]
_[9] harvtxt
_[10] harvtxt
_[11] harvtxt
_[12] harvtxt
_[12] harvtxt
_[13] 서적 Shortest Connectivity: An Introduction with Applications in Phylogeny https://books.google[...] Springer
_[14] 간행물 Four-point Fermat location problems revisited. New proofs and extensions of old results http://mosi.vub.ac.b[...] 2017-11-17
_[15] harvtxt
_[16] 웹사이트 Epsilon-nets and VC-dimension http://ilex.iit.cnr.[...]

본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com