La geometría de la distancia es la caracterización y el estudio de conjuntos de puntos basados únicamente en valores dados de las distancias entre pares de miembros. [1] [2] [3] De manera más abstracta, se trata del estudio de espacios semimétricos y las transformaciones isométricas entre ellos. Desde este punto de vista, se puede considerar como un tema dentro de la topología general . [4]
Históricamente, el primer resultado en la geometría de la distancia es la fórmula de Heron en el siglo I d.C. La teoría moderna comenzó en el siglo XIX con el trabajo de Arthur Cayley , seguida de desarrollos más extensos en el siglo XX por Karl Menger y otros.
Los problemas de geometría de distancia surgen cuando se necesita inferir la forma de una configuración de puntos ( posiciones relativas ) a partir de las distancias entre ellos, como en biología , [4] redes de sensores , [5] topografía , navegación , cartografía y física .
Introducción y definiciones
Los conceptos de geometría de distancia se explicarán primero describiendo dos problemas particulares.
Considere tres estaciones de radio terrestres A, B, C, cuyas ubicaciones se conocen. Un receptor de radio se encuentra en un lugar desconocido. El tiempo que tarda una señal de radio en viajar desde las estaciones hasta el receptor,, se desconocen, pero las diferencias horarias, y , son conocidos. De ellos se conocen las diferencias de distancia y , a partir de la cual se puede encontrar la posición del receptor.
Segundo problema: reducción de dimensiones
En el análisis de datos , a menudo se le da una lista de datos representados como vectores., y es necesario averiguar si se encuentran dentro de un subespacio afín de baja dimensión. Una representación de datos de baja dimensión tiene muchas ventajas, como ahorrar espacio de almacenamiento, tiempo de cálculo y brindar una mejor comprensión de los datos.
Definiciones
Ahora formalizamos algunas definiciones que surgen naturalmente al considerar nuestros problemas.
Espacio semimétrico
Dada una lista de puntos en , , podemos especificar arbitrariamente las distancias entre pares de puntos mediante una lista de , . Esto define un espacio semimétrico : un espacio métrico sin desigualdad triangular .
Explícitamente, definimos un espacio semimétrico como un conjunto no vacío equipado con un semimétrico tal que, para todos ,
- Positividad: si y solo si .
- Simetría: .
Cualquier espacio métrico es a fortiori un espacio semimétrico. En particular,, la -Espacio euclidiano dimensional , es el espacio métrico canónico en geometría de distancia.
La desigualdad del triángulo se omite en la definición, porque no queremos imponer más restricciones a las distancias. que el mero requisito de que sean positivos.
En la práctica, los espacios semimétricos surgen naturalmente de mediciones inexactas. Por ejemplo, dados tres puntos en una linea, con , una medición inexacta podría dar , violando la desigualdad del triángulo.
Incrustación isométrica
Dados dos espacios semimétricos, , una incrustación isométrica de a es un mapa que conserva la semimétrica, es decir, para todos , .
Por ejemplo, dado el espacio semimétrico finito definido anteriormente, una incrustación isométrica se define por puntos , tal que para todos .
Independencia afín
Dados los puntos , se definen como afinamente independientes , si no pueden caber dentro de un solo-subespacio afín dimensional de , para cualquier , si el - simplex abarcan,, tiene positivo -volumen, es decir, .
En general, cuando , son afinamente independientes, ya que un n-simplex genérico no es degenerado. Por ejemplo, 3 puntos en el plano, en general, no son colineales, porque el triángulo que abarcan no degenera en un segmento de línea. De manera similar, 4 puntos en el espacio, en general, no son coplanares, porque el tetraedro que abarcan no degenera en un triángulo plano.
Cuándo , deben ser afinamente dependientes. Esto se puede ver al señalar que cualquier-simplex que cabe dentro debe ser "plano".
Determinantes de Cayley-Menger
Los determinantes de Cayley-Menger , llamados así por Arthur Cayley y Karl Menger, son determinantes de matrices de distancias entre conjuntos de puntos.
Dejar ser n + 1 puntos en un espacio semimétrico, su determinante Cayley-Menger está definido por
Si , luego forman los vértices de un n-simplex (posiblemente degenerado ) en . Se puede demostrar que [6] el volumen n-dimensional del simplex satisface
.
Tenga en cuenta que, para el caso de , tenemos , lo que significa que el "volumen 0-dimensional" de un 0-simplex es 1, es decir, hay 1 punto en un 0-simplex.
son afinamente independientes si , es decir, . Por tanto, los determinantes de Cayley-Menger proporcionan una forma computacional de demostrar la independencia afín.
Si , entonces los puntos deben ser afinamente dependientes, por lo tanto . El artículo de Cayley de 1841 estudió el caso especial de, es decir, 5 puntos cualesquiera en el espacio tridimensional debe tener .
Historia
El primer resultado en geometría de distancias es la fórmula de Heron , del siglo I d.C., que da el área de un triángulo a partir de las distancias entre sus 3 vértices. La fórmula de Brahmagupta , del siglo VII d.C., la generaliza a cuadriláteros cíclicos . Tartaglia , del siglo XVI d.C., lo generalizó para dar el volumen de tetraedro a partir de las distancias entre sus 4 vértices.
La teoría moderna de la geometría de la distancia comenzó con Authur Cayley y Karl Menger . [7] Cayley publicó el determinante de Cayley en 1841, [8] que es un caso especial del determinante general de Cayley-Menger. Menger demostró en 1928 un teorema de caracterización de todos los espacios semimétricos que son incrustables isométricamente en el espacio euclidiano n - dimensional. . [9] [10] En 1931, Menger usó relaciones de distancia para dar un tratamiento axiomático de la geometría euclidiana. [11]
El libro de Leonard Blumenthal [12] ofrece una descripción general de la geometría de la distancia a nivel de posgrado, gran parte de la cual se trata en inglés por primera vez cuando se publicó.
Teorema de caracterización de Menger
Menger demostró el siguiente teorema de caracterización de espacios semimétricos: [2]
Un espacio semimétrico es incrustable isométricamente en el -espacio euclidiano dimensional , pero no en para cualquier , si y solo si:
- contiene un subconjunto de puntos que es isométrica con una afinidad independiente -punto subconjunto de ;
- alguna subconjunto de puntos , obtenido sumando dos puntos adicionales de a , es congruente con un -punto subconjunto de .
Una prueba de este teorema en una forma ligeramente debilitada (para espacios métricos en lugar de espacios semimétricos) está en. [13]
Caracterización mediante determinantes de Cayley-Menger
Los siguientes resultados se prueban en el libro de Blumethal. [12]
Incrustar puntos en
Dado un espacio semimétrico , con , y , , una incrustación isométrica de dentro es definido por , tal que para todos .
Una vez más, uno se pregunta si existe tal incrustación isométrica para .
Una condición necesaria es fácil de ver: para todos , dejar ser el k -simplex formado por, luego
Lo contrario también es válido. Es decir, si por todos,
,
entonces existe tal incrustación.
Además, tal incrustación es única hasta la isometría en . Es decir, dadas dos incrustaciones isométricas cualesquiera definidas por, y , existe una isometría (no necesariamente única) , tal que para todos . Semejante es único si y solo si , es decir, son afinamente independientes.
Incrustar y puntos
Si puntos se puede incrustar en como , entonces, aparte de las condiciones anteriores, una condición adicional necesaria es que el -simplex formado por , no debe tener -volumen dimensional. Es decir,.
Lo contrario también es válido. Es decir, si por todos,
,
y
,
entonces existe tal incrustación.
Para incrustar puntos en , las condiciones necesarias y suficientes son similares:
- Para todos , ;
- ;
- ;
- .
Incrustar arbitrariamente muchos puntos
La caso resulta ser suficiente en general.
En general, dado un espacio semimétrico , se puede incrustar isométricamente en si y solo si existe , tal que, para todos , , y para cualquier ,
- ;
- ;
- .
Y tal incrustación es única hasta la isometría en .
Además, si , entonces no se puede incrustar isométricamente en ningún . Y tal incrustación es única hasta una isometría única en.
Por lo tanto, los determinantes de Cayley-Menger brindan una forma concreta de calcular si un espacio semimétrico se puede incrustar en , para algunos finitos , y si es así, cuál es el mínimo .
Aplicaciones
Hay muchas aplicaciones de la geometría de distancias. [3]
En las redes de telecomunicaciones como el GPS se conocen las posiciones de algunos sensores (que se llaman anclas) y también se conocen algunas de las distancias entre sensores: el problema es identificar las posiciones de todos los sensores. [5] La navegación hiperbólica es una tecnología anterior al GPS que utiliza geometría de distancia para localizar barcos en función del tiempo que tardan las señales en llegar a las anclas.
Hay muchas aplicaciones en química. [4] [12] Técnicas como la RMN pueden medir distancias entre pares de átomos de una molécula dada, y el problema es inferir la forma tridimensional de la molécula a partir de esas distancias.
Algunos paquetes de software para aplicaciones son:
- DGSOL . Resuelve problemas de geometría de grandes distancias en el modelado macromolecular .
- Xplor-NIH . Basado en X-PLOR , para determinar la estructura de moléculas basándose en datos de experimentos de RMN. Resuelve problemas de geometría de distancia con métodos heurísticos (como Recocido simulado ) y métodos de búsqueda local (como Minimización de gradiente conjugado ).
- TINKER . Modelado y diseño molecular. Puede resolver problemas de geometría de distancia.
- SNLSDPclique . Código MATLAB para localizar sensores en una red de sensores en función de las distancias entre los sensores.
Ver también
- Matriz de distancia euclidiana
- Escala multidimensional (una técnica estadística utilizada cuando las distancias se miden con errores aleatorios)
- Espacio métrico
- Fórmula de Tartaglia
- Triangulación
- Trilateración
Referencias
- ^ Yemini, Y. (1978). "El problema del posicionamiento - un borrador de un resumen intermedio". Conferencia sobre redes de sensores distribuidos, Pittsburgh .
- ^ a b Liberti, Leo; Lavor, Carlile; MacUlan, Nelson; Mucherino, Antonio (2014). "Aplicaciones y geometría de distancia euclidiana". Revisión SIAM . 56 : 3-69. arXiv : 1205.0349 . doi : 10.1137 / 120875909 .
- ^ a b Mucherino, A .; Lavor, C .; Liberti, L .; Maculan, N. (2013). Geometría de distancia: teoría, métodos y aplicaciones .
- ^ a b c Crippen, GM; Havel, TF (1988). Geometría de distancia y conformación molecular . John Wiley e hijos.
- ^ a b Biswas, P .; Lian, T .; Wang, T .; Ye, Y. (2006). "Algoritmos basados en programación semidefinida para la localización de redes de sensores". Transacciones ACM en redes de sensores . 2 (2): 188–220. doi : 10.1145 / 1149283.1149286 .
- ^ "Volúmenes simplex y el determinante de Cayley-Menger" . www.mathpages.com . Archivado desde el original el 16 de mayo de 2019 . Consultado el 8 de junio de 2019 .
- ^ Liberti, Leo; Lavor, Carlile (2016). "Seis gemas matemáticas de la historia de la geometría de la distancia". Transacciones internacionales en investigación operativa . 23 (5): 897–920. arXiv : 1502.02816 . doi : 10.1111 / itor.12170 . ISSN 1475-3995 .
- ^ Cayley, Arthur (1841). "Sobre un teorema en la geometría de la posición". Revista matemática de Cambridge . 2 : 267-271.
- ^ Menger, Karl (1 de diciembre de 1928). "Untersuchungen über allgemeine Metrik". Mathematische Annalen (en alemán). 100 (1): 75–163. doi : 10.1007 / BF01448840 . ISSN 1432-1807 .
- ^ Blumenthal, LM; Gillam, BE (1943). "Distribución de puntos en n-espacio" . The American Mathematical Monthly . 50 (3): 181. doi : 10.2307 / 2302400 . JSTOR 2302400 .
- ^ Menger, Karl (1931). "Nueva Fundación de la Geometría Euclidiana". Revista Estadounidense de Matemáticas . 53 (4): 721–745. doi : 10.2307 / 2371222 . ISSN 0002-9327 . JSTOR 2371222 .
- ^ a b c Blumenthal, LM (1970). Teoría y aplicaciones de la geometría de la distancia (2ª ed.). Bronx, Nueva York: Chelsea Publishing Company. págs. 90-161. ISBN 978-0-8284-0242-2. LCCN 79113117 .
- ^ Bowers, John C .; Bowers, Philip L. (13 de diciembre de 2017). "A Menger Redux: incrustación de espacios métricos isométricamente en el espacio euclidiano". The American Mathematical Monthly . 124 (7): 621. doi : 10.4169 / amer.math.monthly.124.7.621 . S2CID 50040864 .