라돈의 정리 문서 원본 보기

{{위키데이터 속성 추적}}
[[기하학]]에서, 1921년에 [[요한 라돈]]에 의해 출판된 볼록 집합의 '''라돈의 정리'''는 어떤 '''[[실수|R]]'''<sup>''d''</sup>의 점 ''d''&nbsp;+&nbsp;2 개의 집합이든지 [[볼록 폐포]]가 교차하는 두 [[서로소 집합]]으로 [[집합의 분할|분할]]할 수 있다고 한다. 이 볼록 폐포의 교집합에 있는 점을 집합의 '''라돈 점'''이라고 부른다.

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

== 정의와 구성 ==
[[파일:Radon coefficients.svg|섬네일|300px|평면에서 네 점을 가지는 두 집합(정사각형의 꼭짓점과 정삼각형과 중심), 이 점들의 세 연립 일차 방정식을 푸는 계수들, 그리고 양의 계수로 이루어진 점과 음의 계수로 이루어진 점으로 분리된 라돈 분할을 나타낸 것이다.]]
''d''차원 공간의 점 ''d''&nbsp;+&nbsp;2 개의 어떤 집합 <math>\{x_1,x_2,\dots,x_{d+2}\}\subset \mathbf{R}^d</math>을 고려하자. 그러면 다음 [[연립 일차 방정식]]을 푸는 모두 영이 아닌 계수들의 집합 ''a''<sub>1</sub>,&nbsp;...,&nbsp;''a''<sub>''d''&nbsp;+&nbsp;2</sub>가 존재한다:
:<math> \sum_{i=1}^{d+2} a_i x_i=0,\quad \sum_{i=1}^{d+2} a_i=0,</math>
모르는 것(계수)이 ''d''&nbsp;+&nbsp;2 개가 있고 만족시켜야 하는 방정식은 ''d''&nbsp;+&nbsp;1 개 밖에 없기 때문에(하나하나는 점의 각각의 위치에 관한 것이고 마지막 방정식은 계수의 합이 0이 되어야 한다는 것이다), 0이 아닌 특정한 솔루션 ''a''<sub>1</sub>,&nbsp;...,&nbsp;''a''<sub>''d''&nbsp;+&nbsp;2</sub>을 고정하자. ''I''를 양의 계수를 가지는 점의 집합이라고 하고, ''J''를 음이나 영의 계수를 가지는 점의 집합이라고 하자. 그러면 ''I''와 ''J''는 요구한 점들을 볼록 폐포가 교차하는 두 개의 부분집합으로의 분할을 만족한다.

''I''와 ''J''의 볼록 폐포는 다음 점을 공통으로 포함하기 때문에 교차한다:
:<math>p= \sum_{i\in I}\frac{a_i}{A} x_i=\sum_{j\in J}\frac{-a_j}{A}x_j,</math>
이 때, <math>A</math>는 다음과 같다:
:<math>A=\sum_{i\in I} a_i=-\sum_{j\in J} a_j.</math>
공식의 좌변의 ''p''는 이 점을 ''I''에 있는 점의 [[볼록 조합]]으로 나타내고, 우변은 이것을 ''J''의 점들의 볼록 조합으로 나타낸다. 따라서, ''p''는 양 쪽의 볼록 폐포에 포함되기 때문에 증명이 완료되었다.

이 증명 방법은 [[가우스 소거법]]이나 계수의 연립 일차 방정식을 풀기 위한 다른 효율적인 알고리즘을 사용해서 차원의 [[다항 시간]]에 라돈 점의 효율적인 생성을 가능하게 한다.<ref name="cemst">{{하버드 인용 본문|Clarkson|Eppstein|Miller|Sturtivant|1996}}.</ref>

== 위상 수학적 라돈 정리 ==
라돈의 정리의 [[위상수학]]적인 일반화는 다음을 말한다. ƒ가 (''d''&nbsp;+&nbsp;1)차원 [[단체 (수학)|단체]]에서 ''d''차원 공간까지 [[연속 함수|연속인 어떤 함수]]일 때, 그 단체는 ƒ의 상에서는 교차하지만 서로 교차하지 않는 두 개의 면을 가진다.<ref name="bb">{{harvtxt|Bajmóczy|Bárány|1979}}; {{harvtxt|Matoušek|2003}}.</ref> 라돈의 정리 자체는 ƒ가 단체의 꼭짓점을 ''d''차원 공간의 ''d''&nbsp;+&nbsp;2개의 점으로 가지는 유일한 [[아핀 맵]]인 특수한 경우로 해석될 수 있다.

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

== 적용 ==
평면의 어떤 네 점의 라돈 점은 다른 점들과의 거리의 합이 최소인 [[기하학적 중심]]이다.<ref>{{인용|title=Shortest Connectivity: An Introduction with Applications in Phylogeny|volume=17|series=Combinatorial Optimization|first=Dietmar|last=Cieslik|publisher=Springer|year=2006|isbn=9780387235394|page=6|url=https://books.google.com/books?id=4E0r3oWkn6AC&pg=PA6}}.</ref><ref>{{인용|title=Four-point Fermat location problems revisited. New proofs and extensions of old results|first=Frank|last=Plastria|authorlink=Frank Plastria|year=2006|doi=10.1093/imaman/dpl007|journal=IMA Journal of Management Mathematics|url=http://mosi.vub.ac.be/papers/Plastria2005_Fegnano.pdf|zbl=1126.90046|volume=17|issue=4|pages=387–396|access-date=2017-11-17|archive-date=2016-03-04|archive-url=https://web.archive.org/web/20160304033120/http://mosi.vub.ac.be/papers/Plastria2005_Fegnano.pdf|url-status=}}.</ref>

라돈의 정리는 [[헬리의 정리]]의 볼록 집합의 교점에서 표준적인 증명의 핵심 단계를 만든다;<ref>{{하버드 인용 본문|Matoušek|2002|p=11}}.</ref> 이 증명은 라돈의 정리의 라돈의 원래의 발견의 동기였다.

라돈의 정리는 선형 분리의 면에서 ''d''차원의 점의 [[VC 차원]]을 계산하기 위해서 사용된다. 모든 두 공집합이 아닌 부분집합이 서로 초평면으로 분리할 수 있는 점 ''d''&nbsp;+&nbsp;1개의 집합(예를 들어, 정단체의 점들)이 존재한다. 하지만 어떤 점 ''d''&nbsp;+&nbsp;2 개의 집합이 주어지던지에 관계없이, 라돈 분할의 두 부분집합은 선형적으로 분리할 수 없다. 따라서, 이 계의 VC 차원은 정확히 ''d''&nbsp;+&nbsp;1이다.<ref>[http://ilex.iit.cnr.it/pellegrini/DispenseCorsoRandAlgPisa04/lez9-epsilonnet-draft.ps Epsilon-nets and VC-dimension] {{웹아카이브|url=https://web.archive.org/web/20110722030339/http://ilex.iit.cnr.it/pellegrini/DispenseCorsoRandAlgPisa04/lez9-epsilonnet-draft.ps}}, Lecture Notes by Marco Pellegrini, 2004.</ref>

반복적으로 점 ''d''&nbsp;+&nbsp;2 개의 집합을 반복적으로 라돈 점으로 재배치하는 [[무작위 알고리즘]]은 모든 점 집합의 [[중간점 (기하학)|중간점]]을 점의 개수와 차원에 관한 다항시간 안에 [[근사 알고리즘|근사]]한다.<ref name="cemst"/>

== 각주 ==
{{각주|30em}}

* {{인용
 | last1 = Bajmóczy | first1 = E. G.
 | last2 = Bárány | first2 = I. | author2-link = Imre Bárány
 | doi = 10.1007/BF01896131
 | journal = Acta Mathematica Hungarica
 | pages = 347–350
 | title = A common generalization of Borsuk's and Radon's theorem
 | volume = 34
 | year = 1979}}.
* {{인용
 | last1 = Bandelt | first1 = H.-J.
 | last2 = Pesch | first2 = E.
 | doi = 10.1007/BF01197978
 | issue = 1
 | journal = Archiv der Mathematik
 | pages = 95–98
 | title = A Radon theorem for Helly graphs
 | volume = 52
 | year = 1989}}.
* {{인용
 | last = Chepoi | first = V. D.
 | journal = Mat. Issled.
 |language=러시아어
 | pages = 164–177
 | title = Some properties of the d-convexity in triangulated graphs
 | volume = 87
 | year = 1986}}. As cited by {{harvtxt|Bandelt|Pesch|1989}}.
* {{인용
 | last1 = Clarkson
 | first1 = Kenneth L.
 | author1-link = Kenneth L. Clarkson
 | last2 = Eppstein
 | first2 = David
 | author2-link = David Eppstein
 | last3 = Miller
 | first3 = Gary L.
 | author3-link = Gary Miller (professor)
 | last4 = Sturtivant
 | first4 = Carl
 | last5 = Teng
 | first5 = Shang-Hua
 | author5-link = Shang-Hua Teng
 | year = 1996
 | mr = 1409651
 | issue = 3
 | journal = Int. J. Computational Geometry & Applications
 | pages = 357–377
 | title = Approximating center points with iterated Radon points
 | url = http://www.almaden.ibm.com/u/kclarkson/center/p.pdf
 | volume = 6
 | doi = 10.1142/s021819599600023x
 | access-date = 2017-11-17
 | archive-date = 2012-02-22
 | archive-url = https://web.archive.org/web/20120222031206/http://www.almaden.ibm.com/u/kclarkson/center/p.pdf
 | url-status = 
 }}.
* {{인용
 | last1 = Danzer | first1 = L.
 | last2 = Grünbaum | first2 = B. | author2-link = Branko Grünbaum
 | last3 = Klee | first3 = V. | author3-link = Victor Klee
 | contribution = Helly's theorem and its relatives
 | pages = 101–179
 | publisher = [[American Mathematical Society]]
 | series = Proc. Symp. Pure Math.
 | title = Convexity
 | url = 
 | volume = 7
 | year = 1963}}.
* {{인용
 | last = Duchet | first = Pierre
 | issue = 3
 | journal = Journal of Combinatorial Theory, Series A
 | pages = 307–316
 | title = Convex sets in graphs. II. Minimal path convexity
 | volume = 44
 | year = 1987
 | doi=10.1016/0095-8956(88)90039-1}}. As cited by {{harvtxt|Bandelt|Pesch|1989}}.
* {{인용
 | last = Eckhoff | first = J.
 | contribution = Helly, Radon, and Carathéodory type theorems
 | location = Amsterdam
 | pages = 389–448
 | publisher = North-Holland
 | title = Handbook of Convex Geometry
 | volume = A, B
 | year = 1993}}.
* {{인용
 | last1 = Kay | first1 = David C.
 | last2 = Womble | first2 = Eugene W.
 | mr = 0310766
 | issue = 2
 | journal = Pacific Journal of Mathematics
 | pages = 471–485
 | title = Axiomatic convexity theory and relationships between the Carathéodory, Helly, and Radon numbers
 | url = http://projecteuclid.org/euclid.pjm/1102970059
 | volume = 38
 | year = 1971
 | doi=10.2140/pjm.1971.38.471}}.
* {{인용
 | last = Matoušek | first = J. | author-link = Jiří Matoušek (mathematician)
 | contribution = 1.3 Radon's Lemma and Helly's Theorem
 | isbn = 978-0-387-95373-1
 | pages = 9–12
 | publisher = Springer-Verlag
 | series = [[Graduate Texts in Mathematics]]
 | title = Lectures on Discrete Geometry
 | volume = 212
 | year = 2002}}.
* {{인용
 | last = Matoušek | first = J. | author-link = Jiří Matoušek (mathematician)
 | contribution = 5.1 Nonembeddability Theorems: An Introduction
 | pages = 88–92
 | publisher = Springer-Verlag
 | title = Using the Borsuk–Ulam Theorem: Lectures on Topological Methods in Combinatorics and Geometry
 | year = 2003}}.
* {{인용
 | last = Radon | first = J. | author-link = Johann Radon
 | doi = 10.1007/BF01464231
 | issue = 1–2
 | journal = [[Mathematische Annalen]]
 | pages = 113–115
 | title = Mengen konvexer Körper, die einen gemeinsamen Punkt enthalten
 | volume = 83
 | year = 1921}}.
* {{인용
 | last = Tverberg | first = H. | author-link = Helge Tverberg
 | journal = [[Journal of the London Mathematical Society]]
 | pages = 123–128
 | title = A generalization of Radon's theorem
 | url = http://jlms.oxfordjournals.org/cgi/reprint/s1-41/1/123.pdf
 | volume = 41
 | year = 1966
 | doi=10.1112/jlms/s1-41.1.123}}.

[[분류:볼록기하학 정리]]
[[분류:Geometric transversal theory]]
[[분류:이산기하학 정리]]
[[분류:볼록 껍질]]