en>Niceguyedc: WPCleaner v1.14 - Repaired 1 link to disambiguation page - (You can help) - Hyperbolic plane

2012-07-29T05:55:04Z

WPCleaner v1.14 - Repaired 1 link to disambiguation page - (You can help) - Hyperbolic plane

New page

In [[geometry]], '''Radon's theorem''' on [[convex set]]s, named after [[Johann Radon]], states that any set of ''d'' + 2 points in '''[[real number|R]]'''''d'' can be [[partition of a set|partitioned]] into two (disjoint) sets whose [[convex hull]]s intersect. A point in the intersection of these hulls is called a '''Radon point''' of the set.

For example, in the case ''d'' = 2, any set of four points in the [[Euclidean plane]] can be partitioned in one of two ways. It may form a triple and a singleton, where the convex hull of the triple (a triangle) contains the singleton; alternatively, it may form two pairs of points that form the endpoints of two intersecting [[line segment]]s.

==Proof and construction==
[[File:Radon coefficients.svg|thumb|300px|Two sets of four points in the plane (the vertices of a square and an equilateral triangle with its centroid), the multipliers solving the system of three linear equations for these points, and the Radon partitions formed by separating the points with positive multipliers from the points with negative multipliers.]]
Consider any set <math>\{x_1,x_2,\dots,x_{d+2}\}\subset \mathbf{R}^d</math> of ''d'' + 2 points in ''d''-dimensional space. Then there exists a set of multipliers ''a''1, ..., ''a''''d'' + 2, not all of which are zero, solving the [[system of linear equations]]
:<math> \sum_{i=1}^{d+2} a_i x_i=0,\quad \sum_{i=1}^{d+2} a_i=0,</math>
because there are ''d'' + 2 unknowns (the multipliers) but only ''d'' + 1 equations that they must satisfy (one for each coordinate of the points, together with a final equation requiring the sum of the multipliers to be zero). Fix some particular nonzero solution ''a''1, ..., ''a''''d'' + 2. Let ''I'' be the set of points with positive multipliers, and let ''J'' be the set of points with multipliers that are negative or zero. Then ''I'' and ''J'' form the required partition of the points into two subsets with intersecting convex hulls.

The convex hulls of ''I'' and ''J'' must intersect, because they both contain the point
:<math>p= \sum_{i\in I}\frac{a_i}{A} x_i=\sum_{j\in J}\frac{-a_j}{A}x_j,</math>
where
:<math>A=\sum_{i\in I} a_i=-\sum_{j\in J} a_j.</math>
The left hand side of the formula for ''p'' expresses this point as a [[convex combination]] of the points in ''I'', and the right hand side expresses it as a convex combination of the points in ''J''. Therefore, ''p'' belongs to both convex hulls, completing the proof.

This proof method allows for the efficient construction of a Radon point, in an amount of time that is [[polynomial time|polynomial]] in the dimension, by using [[Gaussian elimination]] or other efficient algorithms to solve the system of equations for the multipliers.<ref name="cemst">{{harvtxt|Clarkson|Eppstein|Miller|Sturtivant|1996}}.</ref>

==Topological Radon theorem==
A [[topology|topological]] generalization of Radon's theorem states that, if ƒ is any [[continuous function]] from a (''d'' + 1)-dimensional [[simplex]] to ''d''-dimensional space, then the simplex has two disjoint faces whose images under ƒ are not disjoint.<ref name="bb">{{harvtxt|Bajmóczy|Bárány|1979}}; {{harvtxt|Matoušek|2003}}.</ref> Radon's theorem itself can be interpreted as the special case in which ƒ is the unique [[affine map]] that takes the vertices of the simplex to a given set of ''d'' + 2 points in ''d''-dimensional space.

More generally, if ''K'' is any (''d'' + 1)-dimensional compact convex set, and ƒ is any continuous function from ''K'' to ''d''-dimensional space, then there exists a linear function ''g'' such that some point where ''g'' achieves its maximum value and some other point where ''g'' achieves its minimum value are mapped by ƒ to the same point. In the case where ''K'' is a simplex, the two simplex faces formed by the maximum and minimum points of ''g'' must then be two disjoint faces whose images have a nonempty intersection. This same general statement, when applied to a [[hypersphere]] instead of a simplex, gives the [[Borsuk–Ulam theorem]], that ƒ must map two opposite points of the sphere to the same point.<ref name="bb"/>

==Applications==
Radon's theorem forms a key step of a standard proof of [[Helly's theorem]] on intersections of convex sets;<ref>{{harvtxt|Matoušek|2002}}, p. 11.</ref> this proof was the motivation for Radon's original discovery of Radon's theorem.

Radon's theorem can also be used to calculate the [[VC dimension]] of ''d''-dimensional points with respect to linear separations. There exist sets of ''d'' + 1 points (for instance, the points of a regular simplex) such that every two nonempty subsets can be separated from each other by a hyperplane. However, no matter which set of ''d'' + 2 points is given, the two subsets of a Radon partition cannot be linearly separated. Therefore, the VC dimension of this system is exactly ''d'' + 1.<ref>[http://ilex.iit.cnr.it/pellegrini/DispenseCorsoRandAlgPisa04/lez9-epsilonnet-draft.ps Epsilon-nets and VC-dimension], Lecture Notes by Marco Pellegrini, 2004.</ref>

A [[randomized algorithm]] that repeatedly replaces sets of ''d'' + 2 points by their Radon point can be used to compute an [[approximation algorithm|approximation]] to a [[centerpoint]] of any point set, in an amount of time that is polynomial in both the number of points and the dimension.<ref name="cemst"/>

==Related concepts==
The Radon point of three points in a one-dimensional space is just their [[median]]. The [[geometric median]] of a set of points is the point minimizing the sum of distances to the points in the set; it generalizes the one-dimensional median and has been studied both from the point of view of [[facility location]] and [[robust statistics]]. For sets of four points in the plane, the geometric median coincides with the Radon point.

Another generalization for partition into ''r'' sets was given by {{harvs|first=Helge|last=Tverberg|authorlink=Helge Tverberg|year=1966|txt}} and is now known as [[Tverberg's theorem]]. It states that for any set of
:<math>(d + 1)(r - 1) + 1\ </math>
points in Euclidean ''d''-space, there is a partition into ''r'' subsets whose convex hulls intersect in at least one common point.

[[Carathéodory's theorem (convex hull)|Carathéodory's theorem]] states that any point in the convex hull of some set of points is also within the convex hull of a subset of at most ''d'' + 1 of the points; that is, that the given point is part of a Radon partition in which it is a singleton. One proof of Carathéodory's theorem uses a technique of examining solutions to systems of linear equations, similar to the proof of Radon's theorem, to eliminate one point at a time until at most ''d'' + 1 remain.

Concepts related to Radon's theorem have also been considered for [[antimatroid|convex geometries]], families of finite sets with the properties that the intersection of any two sets in the family remains in the family, and that the [[empty set]] and the union of all the sets belongs to the family. In this more general context, the convex hull of a set ''S'' is the intersection of the family members that contain ''S'', and the Radon number of a space is the smallest ''r'' such that any ''r'' points have two subsets whose convex hulls intersect. Similarly, one can define the Helly number ''h'' and the Carathéodory number ''c'' by analogy to their definitions for convex sets in Euclidean spaces, and it can be shown that these numbers satisfy the inequalities ''h'' < ''r'' ≤ ''ch'' + 1.<ref>{{harvtxt|Kay|Womble|1971}}.</ref>

In an arbitrary [[undirected graph]], one may define a convex set to be a set of vertices that includes every [[induced subgraph|induced]] [[path graph|path]] connecting a pair of vertices in the set. With this definition, every set of ω + 1 vertices in the graph can be partitioned into two subsets whose convex hulls intersect, and ω + 1 is the minimum number for which this is possible, where ω is the [[clique number]] of the given graph.<ref>{{harvtxt|Duchet|1987}}.</ref> For related results involving [[shortest path]]s instead of induced paths see {{harvtxt|Chepoi|1986}} and {{harvtxt|Bandelt|Pesch|1989}}.

==Notes==
{{reflist|2}}

==References==

*{{citation
| 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}}.
*{{citation
| 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}}.
*{{citation
| last = Chepoi | first = V. D.
| journal = Mat. Issled.
| language = Russian
| 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 = 97h:65010
| 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}}.
*{{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}}. 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}}.
*{{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
| year = 2003}}.
*{{citation
| 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}}.
*{{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}}.

[[Category:Theorems in discrete geometry]]
[[Category:Theorems in convex geometry]]
[[Category:Convex hulls]]
[[Category:Geometric transversal theory]]

Ultraparallel theorem - Revision history

en>Niceguyedc: WPCleaner v1.14 - Repaired 1 link to disambiguation page - (You can help) - Hyperbolic plane