라돈의 정리

기하학에서, 1921년에 요한 라돈에 의해 출판된 볼록 집합의 라돈의 정리는 어떤 R^d의 점 d + 2 개의 집합이든지 볼록 폐포가 교차하는 두 서로소 집합으로 분할할 수 있다고 한다. 이 볼록 폐포의 교집합에 있는 점을 집합의 라돈 점이라고 부른다.

예를 들어, d = 2인 경우, 유클리드 평면에 있는 어떤 네 점의 집합은 두 방법 중 하나로 나뉘어 질 수 있다. 이것은 세 개의 집합 (삼각형)의 볼록 폐포가 하나의 집합을 포함하는 세 개의 집합과 한 개의 집합을 만들 수 있다; 대신에 두 개의 선분이 교차하도록 하는 양 끝점을 이루는 두 쌍의 점을 만들 수 있다.

정의와 구성

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

d차원 공간의 점 d + 2 개의 어떤 집합 $\{x_{1},x_{2},\dots ,x_{d+2}\}\subset \mathbf {R} ^{d}$을 고려하자. 그러면 다음 연립 일차 방정식을 푸는 모두 영이 아닌 계수들의 집합 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에 있는 점의 볼록 조합으로 나타내고, 우변은 이것을 J의 점들의 볼록 조합으로 나타낸다. 따라서, p는 양 쪽의 볼록 폐포에 포함되기 때문에 증명이 완료되었다.

이 증명 방법은 가우스 소거법이나 계수의 연립 일차 방정식을 풀기 위한 다른 효율적인 알고리즘을 사용해서 차원의 다항 시간에 라돈 점의 효율적인 생성을 가능하게 한다.

위상 수학적 라돈 정리

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

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

적용

평면의 어떤 네 점의 라돈 점은 다른 점들과의 거리의 합이 최소인 기하학적 중심이다.

라돈의 정리는 헬리의 정리의 볼록 집합의 교점에서 표준적인 증명의 핵심 단계를 만든다; 이 증명은 라돈의 정리의 라돈의 원래의 발견의 동기였다.

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

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

참조

• Bajmóczy, E. G.; Bárány, I. (1979), “A common generalization of Borsuk's and Radon's theorem”, 《Acta Mathematica Hungarica》 34: 347–350, doi:10.1007/BF01896131 .
• Bandelt, H.-J.; Pesch, E. (1989), “A Radon theorem for Helly graphs”, 《Archiv der Mathematik》 52 (1): 95–98, doi:10.1007/BF01197978 .
• Chepoi, V. D. (1986), “Some properties of the d-convexity in triangulated graphs”, 《Mat. Issled.》 (러시아어) 87: 164–177 . As cited by Bandelt & Pesch (1989).
• Clarkson, Kenneth L.; Eppstein, David; Miller, Gary L.; Sturtivant, Carl; Teng, Shang-Hua (1996), “Approximating center points with iterated Radon points” (PDF), 《Int. J. 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. 7, American Mathematical Society, 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-1 . As cited by Bandelt & Pesch (1989).
• Eckhoff, J. (1993), 〈Helly, Radon, and Carathéodory type theorems〉, 《Handbook of Convex Geometry》 A, B, Amsterdam: North-Holland, 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 212, Springer-Verlag, 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, 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 .
• 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 .