Teorema de Radon

En geometría , el teorema de Radon sobre conjuntos convexos , publicado por Johann Radon en 1921, establece que:

Cualquier conjunto de d  +  2 puntos en R ^d puede dividirse en dos conjuntos cuyos envolventes convexos se intersecan.

Un punto en la intersección de estas envolturas convexas se denomina punto de Radon del conjunto.

Por ejemplo, en el caso d  =  2, cualquier conjunto de cuatro puntos en el plano euclidiano puede dividirse de dos maneras. Puede formar una terna y un único, donde la envoltura convexa de la terna (un triángulo) contiene el único; alternativamente, puede formar dos pares de puntos que constituyen los extremos de dos segmentos de línea que se intersecan .

Considere cualquier conjunto${\displaystyle X=\{x_{1},x_{2},\dots ,x_{d+2}\}\subset \mathbf {R} ^{d}}$de d  +  2 puntos en un espacio d -dimensional. Entonces existe un conjunto de multiplicadores a ₁ ,  ..., a _{d + 2} , no todos los cuales son cero, que resuelven el sistema de ecuaciones lineales.   

${\displaystyle \sum _{i=1}^{d+2}a_{i}x_{i}=0,\quad \sum _{i=1}^{d+2}a_{i}=0,}$

porque hay d  +  2 incógnitas (los multiplicadores) pero solo d  +  1 ecuaciones que deben satisfacer (una para cada coordenada de los puntos, junto con una ecuación final que requiere que la suma de los multiplicadores sea cero). Fijemos alguna solución particular no nula a ₁ ,  ..., a _{d + 2} . Sea   ${\displaystyle I\subsetequ X}$Sea el conjunto de puntos con multiplicadores positivos, y sea${\displaystyle J=X\setminus I}$Sea el conjunto de puntos con multiplicadores negativos o cero. Entonces${\displaystyle I}$y${\displaystyle J}$formar la partición requerida de los puntos en dos subconjuntos con envolventes convexas que se intersecan.

Las envolturas convexas de${\displaystyle I}$y${\displaystyle J}$deben intersecarse, porque ambos contienen el punto

${\displaystyle p=\sum _{x_{i}\in I}{\frac {a_{i}}{A}}x_{i}=\sum _{x_{j}\in J}{\frac {-a_{j}}{A}}x_{j},}$

dónde

${\displaystyle A=\sum _{x_{i}\in I}a_{i}=-\sum _{x_{j}\in J}a_{j}.}$

El lado izquierdo de la fórmula para${\displaystyle p}$expresa este punto como una combinación convexa de los puntos en${\displaystyle I}$y el lado derecho lo expresa como una combinación convexa de los puntos en${\displaystyle J}$. Por lo tanto,${\displaystyle p}$pertenece a ambas envolturas convexas, completando así la demostración.

Este método de demostración permite la construcción eficiente de un punto de Radon, en un tiempo polinomial en la dimensión, mediante el uso de la eliminación gaussiana u otros algoritmos eficientes para resolver el sistema de ecuaciones para los multiplicadores. ^{[ 1 ]}

Una formulación equivalente del teorema de Radon es:

Si ƒ es cualquier función afín de un simplex Δ ^{d+1 de dimensión (} d  +  1) a R ^d , entonces hay dos caras disjuntas de Δ ^d+1 cuyas imágenes bajo ƒ se intersecan.

Son equivalentes porque cualquier función afín en un simplex está determinada unívocamente por las imágenes de sus vértices. Formalmente, sea ƒ una función afín de Δ ^d+1 a R ^d . Sea${\displaystyle v_{1},v_{2},\dots,v_{d+2}}$sean los vértices de Δ ^d+1 , y sea${\displaystyle x_{1},x_{2},\dots ,x_{d+2}}$sean sus imágenes bajo ƒ . Por la formulación original, el${\displaystyle x_{1},x_{2},\dots ,x_{d+2}}$puede particionarse en dos subconjuntos disjuntos, por ejemplo ( x _i ) _{i en I} y ( x _j ) _{j en J,} con envoltura convexa superpuesta. Debido a que f es afín, la envoltura convexa de ( x _i ) _{i en I} es la imagen de la cara generada por los vértices ( v _i ) _{i en I} , y de manera similar la envoltura convexa de ( x _j ) j _{en J} es la imagen de la cara generada por los vértices ( v _j ) j _{en j} . Estas dos caras son disjuntas, y sus imágenes bajo f se intersecan, como afirma la nueva formulación. El teorema topológico de Radon generaliza esta formulación. Permite que f sea cualquier función continua, no necesariamente afín: ^{[ 2 ]}

Si ƒ es cualquier función continua de un simplex Δ ^d+1 de dimensión ( d  +  1) a R ^d , entonces hay dos caras disjuntas de Δ ^d+1 cuyas imágenes bajo ƒ se intersecan.

De forma más general, si K es un conjunto compacto convexo de dimensión ( d  +  1) y ƒ es una función continua de K a un espacio de dimensión d , entonces existe una función lineal g tal que un punto donde g alcanza su valor máximo y otro punto donde g alcanza su valor mínimo son mapeados por ƒ al mismo punto. En el caso de que K sea un símplex, las dos caras del símplex formadas por los puntos máximo y mínimo de g deben ser dos caras disjuntas cuyas imágenes tienen una intersección no vacía. Esta misma afirmación general, aplicada a una hiperesfera en lugar de un símplex, da lugar al teorema de Borsuk-Ulam , que establece que ƒ debe mapear dos puntos opuestos de la esfera al mismo punto. ^{[ 2 ]}

El punto de Radon de cuatro puntos cualesquiera en el plano es su mediana geométrica , el punto que minimiza la suma de las distancias a los otros puntos. ^{[ 5 ] [ 6 ]}

El teorema de Radon constituye un paso clave de una demostración estándar del teorema de Helly sobre intersecciones de conjuntos convexos; ^{[ 7 ]} esta demostración fue la motivación para el descubrimiento original del teorema de Radon por parte de Radon.

El teorema de Radon también puede utilizarse para calcular la dimensión VC de puntos d -dimensionales con respecto a separaciones lineales. Existen conjuntos de d  +  1 puntos (por ejemplo, los puntos de un símplex regular) tales que cualquier par de subconjuntos no vacíos pueden separarse entre sí mediante un hiperplano . Sin embargo, independientemente del conjunto de d  +  2 puntos que se dé, los dos subconjuntos de una partición de Radon no pueden separarse linealmente. Por lo tanto, la dimensión VC de este sistema es exactamente d  +  1. ^{[ 8 ]}

Se puede utilizar un algoritmo aleatorio que reemplaza repetidamente conjuntos de d  + 2 puntos por su punto de Radon para calcular una aproximación al punto central de cualquier conjunto de puntos, en un tiempo polinomial tanto en el número de puntos como en la dimensión. ^{[ 1 ]} 

Mediana geométrica . El punto de Radon de tres puntos en un espacio unidimensional es precisamente su mediana . La mediana geométrica de un conjunto de puntos es el punto que minimiza la suma de las distancias a los puntos del conjunto; generaliza la mediana unidimensional y se ha estudiado tanto desde el punto de vista de la localización de instalaciones como de la estadística robusta . Para conjuntos de cuatro puntos en el plano, la mediana geométrica coincide con el punto de Radon.

Teorema de Tverberg . Helge Tverberg ( 1966 ) dio una generalización para la partición en r conjuntos , que ahora se conoce como el teorema de Tverberg . Este establece que para cualquier conjunto de ${\displaystyle (d+1)(r-1)+1\ }$Si hay puntos en el espacio euclidiano d , existe una partición en r subconjuntos cuyas envolturas convexas se intersecan en al menos un punto común.

El teorema de Carathéodory establece que cualquier punto dentro de la envoltura convexa de un conjunto de puntos también se encuentra dentro de la envoltura convexa de un subconjunto de como máximo d  + 1 puntos; es decir, que el punto dado forma parte de una partición de Radon en la que es un elemento único. Una demostración del teorema de Carathéodory utiliza una técnica de análisis de soluciones de sistemas de ecuaciones lineales, similar a la demostración del teorema de Radon, para eliminar un punto a la vez hasta que queden como máximo d  + 1.

Geometrías convexas . También se han considerado conceptos relacionados con el teorema de Radon para geometrías convexas , familias de conjuntos finitos con las propiedades de que la intersección de cualesquiera dos conjuntos de la familia permanece en la familia, y que el conjunto vacío y la unión de todos los conjuntos pertenecen a la familia. En este contexto más general, la envoltura convexa de un conjunto S es la intersección de los miembros de la familia que contienen a S , y el número de Radon de un espacio es el menor r tal que cualesquiera r puntos tienen dos subconjuntos cuyas envolturas convexas se intersecan. De manera similar, se puede definir el número de Helly h y el número de Carathéodory c por analogía con sus definiciones para conjuntos convexos en espacios euclidianos, y se puede demostrar que estos números satisfacen las desigualdades h  < r ≤ ch + 1. ^{[ 9 ]}     

Teorema de Radon para grafos . En un grafo no dirigido arbitrario , se puede definir un conjunto convexo como un conjunto de vértices que incluye cada camino inducido que conecta un par de vértices en el conjunto. Con esta definición, cada conjunto de ω + 1 vértices en el grafo se puede particionar en dos subconjuntos cuyas envolturas convexas se intersecan, y ω + 1 es el número mínimo para el cual esto es posible, donde ω es el número de clique del grafo dado. ^{[ 10 ]} Para resultados relacionados que involucran caminos más cortos en lugar de caminos inducidos, véanse Chepoi (1986) y Bandelt & Pesch (1989) .    

• Bajmóczy, EG; Bárány, I. (1979), "Una generalización común del teorema de Borsuk y Radón", Acta Mathematica Hungarica , 34 ( 3– 4): 347– 350, doi : 10.1007/BF01896131 , S2CID 12971298 .
• Bandelt, H.-J.; Pesch, E. (1989), "Un teorema del radón para gráficos de Helly", Archiv der Mathematik , 52 (1): 95– 98, doi : 10.1007/BF01197978 , S2CID 120983560 .
• Chepoi, VD ( 1986), "Algunas propiedades de la d-convexidad en grafos triangulados", Mat. Issled. (en ruso), 87 : 164–177. Según lo citado por Bandelt y Pesch (1989) .
• Clarkson, Kenneth L .; Eppstein, David ; Miller, Gary L .; Sturtivant, Carl; Teng, Shang-Hua (1996), "Aproximación de puntos centrales con puntos de Radon iterados" , International Journal of Computational Geometry & Applications , 6 (3): 357–377 , doi : 10.1142/s021819599600023x , MR 1409651 .
• Danzer, L.; Grünbaum, B .; Klee, V. (1963), " El teorema de Helly y sus variantes", Convexity , Proc. Symp. Pure Math., vol.  7, American Mathematical Society , pp. 101–179 .
• Duchet, Pierre (1987), "Conjuntos convexos en grafos. II. Convexidad de caminos mínimos", Journal of Combinatorial Theory, Series A , 44 (3): 307–316 , doi : 10.1016/0095-8956(88)90039-1. Según lo citado por Bandelt y Pesch (1989) .
• Eckhoff, J. ( 1993), "Teoremas de tipo Helly, Radon y Carathéodory", Manual de Geometría Convexa , vol.  A, B, Ámsterdam: North-Holland, págs. 389–448 .
• Kay, David C.; Womble, Eugene W. (1971), "Teoría de la convexidad axiomática y relaciones entre los números de Carathéodory, Helly y Radon" , Pacific Journal of Mathematics , 38 (2): 471–485 , doi : 10.2140/pjm.1971.38.471 , MR 0310766 .
• Matoušek, J. (2002), "1.3 Lema de Radon y teorema de Helly", Lecciones de geometría discreta , Textos de posgrado en matemáticas , vol.  212, Springer-Verlag, pp. 9–12 , ISBN  978-0-387-95373-1.
• Matoušek, J. (2003), "5.1 Teoremas de no incrustabilidad: una introducción", Uso del teorema de Borsuk-Ulam: lecciones sobre métodos topológicos en combinatoria y geometría , Springer-Verlag, pp. 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 , S2CID 121627696 .
• Tverberg, H. (1966), "Una generalización del teorema de Radon", Journal of the London Mathematical Society , 41 : 123–128 , doi : 10.1112/jlms/s1-41.1.123.