Xem mã nguồn của Định lý Radon

Trong [[hình học]], '''định lý Radon''' về các [[tập hợp lồi]], đặt tên theo [[Johann Radon]], khẳng định rằng mọi tập hợp gồm ''d''&nbsp;+&nbsp;2 điểm trong '''[[số thực|R]]'''<sup>''d''</sup> đều có thể chia thành hai tập hợp con không giao nhau có [[bao lồi]] giao nhau. Mỗi điểm nằm trong phần giao của hai bao lồi được gọi là một '''điểm Radon''' của tập hợp ban đầu.

Ví dụ, trong trường hợp ''d''&nbsp;=&nbsp;2, mọi tập hợp gồm 4 điểm trên [[mặt phẳng]] đều có thể được phân chia theo một trong hai cách sau:
* một tập chứa 3 điểm và một tập chứa đúng 1 điểm, bao lồi (hình [[tam giác]]) của tập thứ nhất chứa điểm trong tập còn lại
* hai cặp điểm sao cho các đoạn thẳng nối mỗi cặp cắt nhau.

==Chứng minh và cách xây dựng==
[[Tập tin:Radon coefficients.svg|nhỏ|300px|Hai ví dụ của tập hợp chứa 4 điểm trên mặt phẳng (các đỉnh của một hình vuông và các đỉnh của một tam giác đều cùng với trọng tâm của tam giác), các hệ số là lời giải cho hệ phương trình tuyến tính của tọa độ các điểm này, và phân chia Radon được xác định bởi dấu của các hệ số: các điểm có hệ số dương tạo thành một tập và các điểm còn lại tạo thành tập thứ hai.]]

Xét một tập <math>\{x_1,x_2,\dots,x_{d+2}\}\subset \mathbf{R}^d</math> bất kì gồm ''d''&nbsp;+&nbsp;2 điểm trong không gian ''d'' chiều. Tồn tại các hệ số ''a''<sub>1</sub>,&nbsp;...,&nbsp;''a''<sub>''d''&nbsp;+&nbsp;2</sub>, sao cho không phải tất cả đều bằng 0, và là lời giải cho [[hệ phương trình tuyến tính]] sau đây
:<math> \sum_{i=1}^{d+2} a_i x_i=0,\quad \sum_{i=1}^{d+2} a_i=0,</math>
do chỉ có ''d''&nbsp;+&nbsp;2 ẩn số (các hệ số) nhưng chỉ có ''d''&nbsp;+&nbsp;1 phương trình (một phương trình cho mỗi tọa độ cùng với một phương trình yêu cầu tổng các hệ số bằng 0). Chọn một lời giải bất kì ''a''<sub>1</sub>,&nbsp;...,&nbsp;''a''<sub>''d''&nbsp;+&nbsp;2</sub>. Đặt ''I'' là tập hợp các điểm có hệ số dương, và ''J'' là tập hợp các điểm có hệ số nhỏ hơn hoặc bằng 0. Khi đó ''I'' và ''J'' tạo thành phân chia cần tìm với bao lồi giao nhau.

Bao lồi của ''I'' và ''J'' giao nhau do chúng cùng chứa điểm
:<math>p= \sum_{i\in I}\frac{a_i}{A} x_i=\sum_{j\in J}\frac{-a_j}{A}x_j,</math>
trong đó
:<math>A=\sum_{i\in I} a_i=-\sum_{j\in J} a_j.</math>
Vế trái của công thức cho ''p'' được viết dưới dạng [[tổ hợp lồi]] của các điểm trong ''I'', và vế phải viết nó dưới dạng tổ hợp lồi của các điểm trong ''J''. Do đó ''p'' nằm trong cả hai bao lồi.

Chứng minh này cũng cho một thuật toán tìm điểm Radon trong [[thời gian đa thức]] của số chiều, bằng cách sử dụng [[phép khử Gauss]] hoặc các thuật toán hiệu quả khác để giải hệ phương trình tuyến tính.<ref name="cemst">{{harvtxt|Clarkson|Eppstein|Miller|Sturtivant|1996}}.</ref>

==Định lý Radon tô pô==
Một tổng quát hóa của định lý Radon trong [[tô pô]] là: nếu ƒ là một [[hàm liên tục]] từ một [[đơn hình]] (''d''&nbsp;+&nbsp;1) chiều đến một không gian ''d'' chiều, thì đơn hình có hai mặt không giao nhau nhưng ảnh của chúng theo ƒ lại giao nhau.<ref name="bb">{{harvtxt|Bajmóczy|Bárány|1979}}; {{harvtxt|Matoušek|2003}}.</ref> Định lý Radon là một trường hợp riêng khi ƒ là [[biến đổi afin]] duy nhất ánh xạ các đỉnh của đơn hình tới một tập ''d''&nbsp;+&nbsp;2 điểm cho trước trong không gian ''d'' chiều.

Tổng quát hơn, nếu ''K'' là một tập hợp lồi [[compact]] trong không gian (''d''&nbsp;+&nbsp;1) chiều, và ƒ là một hàm liên tục từ ''K'' tới không gian ''d'' chiều, thì tồn tại một hàm tuyến tính ''g'' sao cho tồn tại hai điểm có cùng một ảnh theo ƒ: tại một điểm ''g'' đạt giá trị lớn nhất và tại điểm kia ''g'' đạt giá trị nhỏ nhất. Trong trường hợp ''K'' là đơn hình, hai mặt tạo bởi các điểm cực trị theo ''g'' là hai mặt không giao nhau nhưng có ảnh giao nhau. Định lý này khi áp dụng cho [[hình cầu]] thay vì đơn hình, cho ta [[định lý Borsuk–Ulam]], rằng tồn tại hai điểm đối nhau trên hình cầu được ƒ  ánh xạ tới cùng một điểm.<ref name="bb"/>

==Ứng dụng==
Định lý Radon có thể dùng để chứng minh [[định lý Helly]] về giao của các tập hợp lồi.<ref>{{harvtxt|Matoušek|2002}}, tr. 11.</ref> Chứng minh này là động lực ban đầu cho Radon tìm ra định lý Radon.

Định lý Radon cũng có thể dùng để tính [[chiều VC]] của tập các điểm ''d'' chiều đối với các phân chia bằng siêu phẳng. Tồn tại ''d''&nbsp;+&nbsp;1 điểm (chẳng hạn các đỉnh của một đơn hình đều) sao cho mọi tập con khác rỗng đều có thể được phân chia bởi một siêu phẳng. Tuy nhiên với bất kì một tập hợp ''d''&nbsp;+&nbsp;2 điểm nào, hai tập hợp trong phân chia Radon không thể được chia đôi bởi siêu phẳng nào. Do đó, chiều VC trong trường hợp này là ''d''&nbsp;+&nbsp;1.<ref>[http://ilex.iit.cnr.it/pellegrini/DispenseCorsoRandAlgPisa04/lez9-epsilonnet-draft.ps Epsilon-nets and VC-dimension] {{Webarchive|url=https://web.archive.org/web/20110722030339/http://ilex.iit.cnr.it/pellegrini/DispenseCorsoRandAlgPisa04/lez9-epsilonnet-draft.ps |date = ngày 22 tháng 7 năm 2011}}, Bài giảng của Marco Pellegrini, 2004.</ref>

Một [[thuật toán ngẫu nhiên]] lặp đi lặp lại việc thay ''d''&nbsp;+&nbsp;2 điểm bằng điểm Radon của chúng có thể dùng để tính [[thuật toán xấp xỉ|xấp xỉ]] "[[tâm điểm]]" của mọi tập điểm, trong thời gian đa thức theo số điểm và số chiều.<ref name="cemst"/>

==Các khái niệm liên quan==
Điểm Radon của ba điểm trong không gian một chiều chính là [[trung vị]]. [[Trung vị hình học]] của một tập điểm là điểm có tổng khoảng cách nhỏ nhất tới tất cả các điểm trong tập hợp.

Một tổng quát hóa cho việc chia thành ''r'' tập hợp được đưa ra bởi {{harvtxt|Tverberg|1966}} và được gọi là [[định lý Tverberg]]. Nó khẳng định rằng với mọi tập hợp<math>(d + 1)(r - 1) + 1\ </math> điểm trong không gian Euclide ''d'' chiều, tồn tại một cách phân chia nó thành ''r'' tập hợp con sao cho giao của bao lồi của tất cả các tập này là khác rỗng.

[[Định lý Carathéodory (bao lồi)|Định lý Carathéodory]] khẳng định rằng mọi điểm nằm trong bao lồi của một tập điểm ''d'' chiều cũng nằm trong bao lồi của một tập con gồm ''d''&nbsp;+&nbsp;1 điểm. Một chứng minh của định lý Carathéodory cũng sử dụng phương pháp xem xét nghiệm của một hệ phương trình tuyến tính, tương tự như trong chứng minh của định lý Radon, để giảm số điểm tạo bao lồi cho tới khi chỉ còn ''d''&nbsp;+&nbsp;1 điểm.

==Ghi chú==
{{Tham khảo}}

==Tham khảo==
{{refbegin|30em}}
*{{citation
 | last1 = Bajmóczy | first1 = E. G.
 | last2 = Bárány | first2 = I. | author2-link = Imre Bárány
 | doi = 10.1007/BF01896131 | doi-access = free
 | journal = [[Acta Mathematica Hungarica]]
 | pages = 347–350
 | title = A common generalization of Borsuk's and Radon's theorem
 | volume = 34
 | issue = 3–4
 | year = 1979}}.
*{{citation
 | last1 = Bandelt | first1 = H.-J.
 | last2 = Pesch | first2 = E.
 | doi = 10.1007/BF01197978 | doi-access = free
 | issue = 1
 | journal = [[Archiv der Mathematik]]
 | pages = 95–98
 | title = A Radon theorem for Helly graphs
 | volume = 52
 | year = 1989}}.
*{{citation
 | last = Chepoi | first = V. D.
 | journal = Mat. Issled.
 | language = ru
 | pages = 164–177
 | title = Some properties of the d-convexity in triangulated graphs
 | volume = 87
 | year = 1986}}. As cited by {{harvtxt|Bandelt|Pesch|1989}}.
*{{citation
 | 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 = International Journal of 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 = 2011-10-11
 | archive-date = 2012-02-22
 | archive-url = https://web.archive.org/web/20120222031206/http://www.almaden.ibm.com/u/kclarkson/center/p.pdf
 }}.
*{{citation
 | 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}}. 
*{{citation
 | 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| doi-access = free
 }}. As cited by {{harvtxt|Bandelt|Pesch|1989}}.
*{{citation
 | 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}}.
*{{citation
 | 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
 | doi-access = free
 }}.
*{{citation
 | 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}}.
*{{citation
 | 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
 | title-link = Using the Borsuk–Ulam Theorem
 | year = 2003}}.
*{{citation
 | last = Radon | first = J. | author-link = Johann Radon
 | doi = 10.1007/BF01464231 | doi-access = free
 | issue = 1–2
 | journal = [[Mathematische Annalen]]
 | pages = 113–115
 | title = Mengen konvexer Körper, die einen gemeinsamen Punkt enthalten
 | volume = 83
 | year = 1921}}
*{{citation
 | 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
 }}
{{refend}}
[[Thể loại:Hình học rời rạc]]
[[Thể loại:Định lý toán học|R]]
[[Thể loại:Bao lồi]]