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 cascos convexos se cruzan. Un punto en la intersección de estos cascos convexos se llama punto Radon del conjunto.
Por ejemplo, en el caso d = 2, cualquier conjunto de cuatro puntos en el plano euclidiano se puede dividir de dos maneras. Puede formar un triple y un singleton, donde el casco convexo del triple (un triángulo) contiene el singleton; alternativamente, puede formar dos pares de puntos que forman los puntos finales de dos segmentos de línea que se cruzan .
Prueba y construcción
![](http://wikiimg.tojsiabtv.com/wikipedia/commons/thumb/4/44/Radon_coefficients.svg/300px-Radon_coefficients.svg.png)
Considere cualquier conjunto de d + 2 puntos en el espacio d -dimensional. Entonces existe un conjunto de multiplicadores a 1 , ..., a d + 2 , no todos los cuales son cero, resolviendo el sistema de ecuaciones lineales
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). Arregle alguna solución particular distinta de cero a 1 , ..., a d + 2 . Dejar sea el conjunto de puntos con multiplicadores positivos, y sea ser el conjunto de puntos con multiplicadores negativos o cero. Luego y Forme la partición requerida de los puntos en dos subconjuntos con cascos convexos que se cruzan.
Los cascos convexos de y deben cruzarse, porque ambos contienen el punto
dónde
El lado izquierdo de la fórmula para expresa este punto como una combinación convexa de los puntos en, y el lado derecho lo expresa como una combinación convexa de los puntos en . Por lo tanto, Pertenece a ambos cascos convexos, completando la prueba.
Este método de prueba permite la construcción eficiente de un punto Radon, en una cantidad de tiempo que es polinomial en la dimensión, usando eliminación gaussiana u otros algoritmos eficientes para resolver el sistema de ecuaciones para los multiplicadores. [1]
Teorema topológico del radón
Una generalización topológica del teorema de Radon establece que, si f es cualquier función continua de un simplex ( d + 1) -dimensional al espacio d -dimensional, entonces el simplex tiene dos caras disjuntas cuyas imágenes bajo f no son disjuntas. [2] El teorema de Radon en sí mismo se puede interpretar como el caso especial en el que f es el mapa afín único que lleva los vértices del simplex a un conjunto dado de d + 2 puntos en el espacio d -dimensional.
De manera más general, si K es cualquier conjunto convexo compacto ( d + 1) -dimensional, y ƒ es cualquier función continua desde K hasta el espacio d -dimensional, entonces existe una función lineal g tal que algún punto donde g alcance su valor máximo y algún otro punto donde g alcanza su valor mínimo son mapeados por ƒ al mismo punto. En el caso de que K sea un simplex, las dos caras simplex formadas por los puntos máximo y mínimo de g deben ser entonces dos caras disjuntas cuyas imágenes tienen una intersección no vacía. Esta misma afirmación general, cuando se aplica a una hiperesfera en lugar de una simplex, da el teorema de Borsuk-Ulam , que ƒ debe mapear dos puntos opuestos de la esfera al mismo punto. [2]
Aplicaciones
El punto Radon de cualquiera de los cuatro puntos en el plano es su mediana geométrica , el punto que minimiza la suma de distancias a los otros puntos. [3] [4]
El teorema de Radon forma un paso clave de una prueba estándar del teorema de Helly sobre intersecciones de conjuntos convexos; [5] esta prueba fue la motivación para el descubrimiento original de Radon del teorema de Radon.
El teorema de Radon también se puede utilizar para calcular la dimensión VC de los puntos d- dimensionales con respecto a las separaciones lineales. Existen conjuntos de puntos d + 1 (por ejemplo, los puntos de un simplex regular) de modo que cada dos subconjuntos no vacíos pueden estar separados entre sí por un hiperplano. Sin embargo, no importa qué conjunto de puntos d + 2 se dé, los dos subconjuntos de una partición de Radon no se pueden separar linealmente. Por lo tanto, la dimensión VC de este sistema es exactamente d + 1. [6]
Se puede utilizar un algoritmo aleatorio que reemplaza repetidamente conjuntos de d + 2 puntos por su punto Radon para calcular una aproximación a un punto central de cualquier conjunto de puntos, en una cantidad de tiempo que es polinomial tanto en el número de puntos como en la dimensión. [1]
Conceptos relacionados
El punto Radon de tres puntos en un espacio unidimensional es solo su mediana . La mediana geométrica de un conjunto de puntos es el punto que minimiza la suma de distancias a los puntos del conjunto; generaliza la mediana unidimensional y se ha estudiado tanto desde el punto de vista de la ubicación de las instalaciones como de las estadísticas sólidas . Para conjuntos de cuatro puntos en el plano, la mediana geométrica coincide con el punto Radon.
Helge Tverberg ( 1966 ) dio otra generalización para la partición en r conjuntos y ahora se conoce como teorema de Tverberg . Afirma que para cualquier conjunto de
puntos en el espacio d euclidiano , hay una partición en r subconjuntos cuyos cascos convexos se cruzan en al menos un punto común.
El teorema de Carathéodory establece que cualquier punto en el casco convexo de algún conjunto de puntos también está dentro del casco convexo de un subconjunto de como máximo d + 1 de los puntos; es decir, que el punto dado es parte de una partición de Radon en la que es un singleton. Una prueba del teorema de Carathéodory utiliza una técnica de examen de soluciones a sistemas de ecuaciones lineales, similar a la prueba del teorema de Radon, para eliminar un punto a la vez hasta que quede como máximo d + 1.
Los conceptos relacionados con el teorema de Radon también se han considerado para geometrías convexas , familias de conjuntos finitos con las propiedades de que la intersección de dos conjuntos cualesquiera 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. familia. En este contexto más general, el casco convexo de un conjunto S es la intersección de los miembros de la familia que contienen S , y el número de radón de un espacio es el r más pequeño, de modo que cualquier r puntos tiene dos subconjuntos cuyos cascos convexos se cruzan. De manera similar, se puede definir el número de Helly hy 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. [7]
En un gráfico arbitrario no dirigido , 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 gráfico se puede dividir en dos subconjuntos cuyos cascos convexos se cruzan, y ω + 1 es el número mínimo para el cual esto es posible, donde ω es el número de clique del gráfico dado. [8] Para obtener resultados relacionados que involucran caminos más cortos en lugar de caminos inducidos, ver Chepoi (1986) y Bandelt & Pesch (1989) .
Notas
- ^ a b Clarkson y col. (1996) .
- ↑ a b Bajmóczy y Bárány (1979) ; Matoušek (2003) .
- ^ Cieslik, Dietmar (2006), Conectividad más corta: una introducción con aplicaciones en filogenia , Optimización combinatoria, 17 , Springer, p. 6, ISBN 9780387235394.
- ^ Plastria, Frank (2006), " Revisión de los problemas de ubicación de Fermat de cuatro puntos. Nuevas pruebas y extensiones de resultados anteriores" (PDF) , IMA Journal of Management Mathematics , 17 (4): 387–396, doi : 10.1093 / imaman / dpl007 , Zbl 1126.90046.
- ^ Matoušek (2002) , p. 11.
- ^ Epsilon-nets y VC-dimension , Lecture Notes de Marco Pellegrini, 2004.
- ^ Kay y Womble (1971) .
- ^ Duchet (1987) .
Referencias
- Bajmóczy, EG; Bárány, I. (1979), "Una generalización común del teorema de Borsuk y Radon", Acta Mathematica Hungarica , 34 (3–4): 347–350, doi : 10.1007 / BF01896131.
- 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.
- Chepoi, VD (1986), "Algunas propiedades de la d-convexidad en gráficos 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 radón iterados" (PDF) , International Journal of Computational Geometry & Applications , 6 (3): 357–377, doi : 10.1142 / s021819599600023x , MR 1409651.
- Danzer, L .; Grünbaum, B .; Klee, V. (1963), "Teorema de Helly y sus parientes", Convexidad , Proc. Symp. Pure Math., 7 , American Mathematical Society , págs. 101–179.
- Duchet, Pierre (1987), "Conjuntos convexos en gráficos. II. Convexidad de trayectoria mínima", Journal of Combinatorial Theory, Serie 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", Handbook of Convex Geometry , A, B , Amsterdam: 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 Carathéodory, Helly y Radon" , Pacific Journal of Mathematics , 38 (2): 471–485, doi : 10.2140 / pjm.1971.38.471 , Señor 0310766.
- Matoušek, J. (2002), "1.3 Lema de Radon y teorema de Helly", Conferencias sobre geometría discreta , Textos de posgrado en matemáticas , 212 , Springer-Verlag, págs. 9-12, ISBN 978-0-387-95373-1.
- Matoušek, J. (2003), "5.1 Teoremas de no incrustabilidad: Introducción", Uso del teorema de Borsuk-Ulam: Conferencias sobre métodos topológicos en combinatoria y geometría , Springer-Verlag, págs. 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.
- Tverberg, H. (1966), "Una generalización del teorema de Radon" (PDF) , Revista de la Sociedad Matemática de Londres , 41 : 123-128, doi : 10.1112 / jlms / s1-41.1.123[ enlace muerto ] .