In
geometry
Geometry (; ) is, with arithmetic, one of the oldest branches of mathematics. It is concerned with properties of space such as the distance, shape, size, and relative position of figures. A mathematician who works in the field of geometry is c ...
, Radon's theorem on
convex set
In geometry, a subset of a Euclidean space, or more generally an affine space over the reals, is convex if, given any two points in the subset, the subset contains the whole line segment that joins them. Equivalently, a convex set or a convex r ...
s, published by
Johann Radon
Johann Karl August Radon (; 16 December 1887 – 25 May 1956) was an Austrian mathematician. His doctoral dissertation was on the calculus of variations (in 1910, at the University of Vienna).
Life
RadonBrigitte Bukovics: ''Biography of Johan ...
in 1921, states that any set of ''d'' + 2 points in
R''d'' can be
partitioned into two sets whose
convex hull
In geometry, the convex hull or convex envelope or convex closure of a shape is the smallest convex set that contains it. The convex hull may be defined either as the intersection of all convex sets containing a given subset of a Euclidean space ...
s intersect. A point in the intersection of these convex 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
In mathematics, the Euclidean plane is a Euclidean space of dimension two. That is, a geometric setting in which two real quantities are required to determine the position of each point ( element of the plane), which includes affine notions of ...
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
In geometry, a line segment is a part of a straight line that is bounded by two distinct end points, and contains every point on the line that is between its endpoints. The length of a line segment is given by the Euclidean distance between ...
s.
Proof and construction
![Radon coefficients](https://upload.wikimedia.org/wikipedia/commons/4/44/Radon_coefficients.svg)
Consider any set
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
In mathematics, a system of linear equations (or linear system) is a collection of one or more linear equations involving the same variable (math), variables.
For example,
:\begin
3x+2y-z=1\\
2x-2y+4z=-2\\
-x+\fracy-z=0
\end
is a system of three ...
:
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
be the set of points with positive multipliers, and let
be the set of points with multipliers that are negative or zero. Then
and
form the required partition of the points into two subsets with intersecting convex hulls.
The convex hulls of
and
must intersect, because they both contain the point
:
where
:
The left hand side of the formula for
expresses this point as a
convex combination
In convex geometry and vector algebra, a convex combination is a linear combination of points (which can be vectors, scalars, or more generally points in an affine space) where all coefficients are non-negative and sum to 1. In other word ...
of the points in
, and the right hand side expresses it as a convex combination of the points in
. Therefore,
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
In mathematics, a polynomial is an expression consisting of indeterminates (also called variables) and coefficients, that involves only the operations of addition, subtraction, multiplication, and positive-integer powers of variables. An exa ...
in the dimension, by using
Gaussian elimination
In mathematics, Gaussian elimination, also known as row reduction, is an algorithm for solving systems of linear equations. It consists of a sequence of operations performed on the corresponding matrix of coefficients. This method can also be used ...
or other efficient algorithms to solve the system of equations for the multipliers.
[.]
Topological Radon theorem
A
topological
In mathematics, topology (from the Greek words , and ) is concerned with the properties of a geometric object that are preserved under continuous deformations, such as stretching, twisting, crumpling, and bending; that is, without closing h ...
generalization of Radon's theorem states that, if ƒ is any
continuous function
In mathematics, a continuous function is a function such that a continuous variation (that is a change without jump) of the argument induces a continuous variation of the value of the function. This means that there are no abrupt changes in value ...
from a (''d'' + 1)-dimensional
simplex
In geometry, a simplex (plural: simplexes or simplices) is a generalization of the notion of a triangle or tetrahedron to arbitrary dimensions. The simplex is so-named because it represents the simplest possible polytope in any given dimension. ...
to ''d''-dimensional space, then the simplex has two disjoint faces whose images under ƒ are not disjoint.
[; .] Radon's theorem itself can be interpreted as the special case in which ƒ is the unique
affine map
In Euclidean geometry, an affine transformation or affinity (from the Latin, ''affinis'', "connected with") is a geometric transformation that preserves lines and parallelism, but not necessarily Euclidean distances and angles.
More generally, ...
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
In mathematics, an -sphere or a hypersphere is a topological space that is homeomorphic to a ''standard'' -''sphere'', which is the set of points in -dimensional Euclidean space that are situated at a constant distance from a fixed point, cal ...
instead of a simplex, gives the
Borsuk–Ulam theorem
In mathematics, the Borsuk–Ulam theorem states that every continuous function from an ''n''-sphere into Euclidean ''n''-space maps some pair of antipodal points to the same point. Here, two points on a sphere are called antipodal if they are in ...
, that ƒ must map two opposite points of the sphere to the same point.
Applications
The Radon point of any four points in the plane is their
geometric median
In geometry, the geometric median of a discrete set of sample points in a Euclidean space is the point minimizing the sum of distances to the sample points. This generalizes the median, which has the property of minimizing the sum of distances ...
, the point that minimizes the sum of distances to the other points.
Radon's theorem forms a key step of a standard proof of
Helly's theorem
Helly's theorem is a basic result in discrete geometry on the intersection of convex sets. It was discovered by Eduard Helly in 1913,. but not published by him until 1923, by which time alternative proofs by and had already appeared. Helly's t ...
on intersections of convex sets; 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
VC may refer to:
Military decorations
* Victoria Cross, a military decoration awarded by the United Kingdom and also by certain Commonwealth nations
** Victoria Cross for Australia
** Victoria Cross (Canada)
** Victoria Cross for New Zealand
* Vic ...
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.
A
randomized algorithm
A randomized algorithm is an algorithm that employs a degree of randomness as part of its logic or procedure. The algorithm typically uses uniformly random bits as an auxiliary input to guide its behavior, in the hope of achieving good performan ...
that repeatedly replaces sets of ''d'' + 2 points by their Radon point can be used to compute an
approximation
An approximation is anything that is intentionally similar but not exactly equality (mathematics), equal to something else.
Etymology and usage
The word ''approximation'' is derived from Latin ''approximatus'', from ''proximus'' meaning ''very ...
to a
centerpoint of any point set, in an amount of time that is polynomial in both the number of points and the dimension.
Related concepts
The Radon point of three points in a one-dimensional space is just their
median
In statistics and probability theory, the median is the value separating the higher half from the lower half of a data sample, a population, or a probability distribution. For a data set, it may be thought of as "the middle" value. The basic fe ...
. The
geometric median
In geometry, the geometric median of a discrete set of sample points in a Euclidean space is the point minimizing the sum of distances to the sample points. This generalizes the median, which has the property of minimizing the sum of distances ...
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 Facility location is a name given to several different problems in computer science and in game theory:
* Facility location problem, the optimal placement of facilities as a function of transportation costs and other factors
* Facility location (co ...
and
robust statistics
Robust statistics are statistics with good performance for data drawn from a wide range of probability distributions, especially for distributions that are not normal. Robust statistical methods have been developed for many common problems, suc ...
. 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 and is now known as
Tverberg's theorem
In discrete geometry, Tverberg's theorem, first stated by , is the result that sufficiently many points in ''d''-dimensional Euclidean space can be partitioned into subsets with intersecting convex hulls. Specifically, for any set of
:(d + 1)(r - ...
. It states that for any set of
:
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 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
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
In mathematics, the empty set is the unique set having no elements; its size or cardinality (count of elements in a set) is zero. Some axiomatic set theories ensure that the empty set exists by including an axiom of empty set, while in other ...
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.
In an arbitrary
undirected graph
In discrete mathematics, and more specifically in graph theory, a graph is a structure amounting to a set of objects in which some pairs of the objects are in some sense "related". The objects correspond to mathematical abstractions called '' v ...
, one may define a convex set to be a set of vertices that includes every
induced
Induce may refer to:
* Induced consumption
* Induced innovation
* Induced character
* Induced coma
* Induced menopause
* Induced metric
* Induced path
* Induced topology
* Induce (musician), American musician
See also
* Inducement (disambiguation ...
path
A path is a route for physical travel – see Trail.
Path or PATH may also refer to:
Physical paths of different types
* Bicycle path
* Bridle path, used by people on horseback
* Course (navigation), the intended path of a vehicle
* Desire p ...
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
In the mathematical area of graph theory, a clique ( or ) is a subset of vertices of an undirected graph such that every two distinct vertices in the clique are adjacent. That is, a clique of a graph G is an induced subgraph of G that is comple ...
of the given graph.
[.] For related results involving
shortest path
In graph theory, the shortest path problem is the problem of finding a path between two vertices (or nodes) in a graph such that the sum of the weights of its constituent edges is minimized.
The problem of finding the shortest path between tw ...
s instead of induced paths see and .
Notes
References
*.
*.
*. As cited by .
*.
*.
*. As cited by .
*.
*.
*.
*.
*.
*{{cbignore, bot=medic.
Theorems in discrete geometry
Theorems in convex geometry
Convex hulls
Geometric transversal theory