Geometría de distancia

La geometría de distancias es la rama de las matemáticas que se ocupa de caracterizar y estudiar conjuntos de puntos basándose únicamente en valores dados de las distancias entre pares de puntos. ^{[1] [2] [3]} De manera más abstracta, es el estudio de espacios semimétricos y las transformaciones isométricas entre ellos. Desde este punto de vista, puede considerarse como un tema dentro de la topología general . ^[4]

Históricamente, el primer resultado en geometría a distancia es la fórmula de Herón 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 siempre que uno 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 distancias se explicarán primero describiendo dos problemas particulares.

Problema de navegación hiperbólica

Primer problema: navegación hiperbólica

Considere tres estaciones de radio terrestres A, B, C, cuyas ubicaciones se conocen. Un receptor de radio se encuentra en un lugar desconocido. Se desconocen los tiempos que tarda una señal de radio en viajar desde las estaciones hasta el receptor, pero se conocen las diferencias de tiempo, y . A partir de ellos se conocen las diferencias de distancia y a partir de las cuales se puede encontrar la posición del receptor. ${\displaystyle t_{A},t_{B},t_{C}}$ ${\displaystyle t_{A}-t_{B}}$ ${\displaystyle t_{A}-t_{C}}$ ${\displaystyle c(t_{A}-t_{B})}$ ${\displaystyle c(t_{A}-t_{C})}$

Segundo problema: reducción de dimensiones .

En el análisis de datos , a menudo se nos proporciona 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. ${\displaystyle \mathbf {v} =(x_{1},\ldots ,x_{n})\in \mathbb {R} ^{n}}$

Definiciones

Ahora formalicemos 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 . ${\displaystyle R=\{P_{0},\ldots ,P_{n}\}}$ ${\displaystyle n\geq 0}$ ${\displaystyle d_{ij}>0}$ ${\displaystyle 0\leq i<j\leq n}$

Explícitamente, definimos un espacio semimétrico como un conjunto no vacío equipado con un espacio semimétrico tal que, para todo , ${\displaystyle R}$ ${\displaystyle d:R\times R\to [0,\infty )}$ ${\displaystyle x,y\in R}$

1. Positividad:   si y sólo si   . ${\displaystyle d(x,y)=0}$ ${\displaystyle x=y}$
2. Simetría: . ${\displaystyle d(x,y)=d(y,x)}$

Cualquier espacio métrico es, a fortiori, un espacio semimétrico. En particular, el espacio euclidiano de dimensiones es el espacio métrico canónico en geometría a distancia. ${\displaystyle \mathbb {R} ^{k}}$ ${\displaystyle k}$

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 positivas. ${\displaystyle d_{ij}}$

En la práctica, los espacios semimétricos surgen naturalmente de mediciones inexactas. Por ejemplo, dados tres puntos en una recta, con , una medición inexacta podría dar , violando la desigualdad del triángulo. ${\displaystyle A,B,C}$ ${\displaystyle d_{AB}=1,d_{BC}=1,d_{AC}=2}$ ${\displaystyle d_{AB}=0.99,d_{BC}=0.98,d_{AC}=2.00}$

Incrustación isométrica

Dados dos espacios semimétricos, una incrustación isométrica de a es un mapa que conserva lo semimétrico, es decir, para todos ,. ${\displaystyle (R,d),(R',d')}$ ${\displaystyle R}$ ${\displaystyle R'}$ ${\displaystyle f:R\to R'}$ ${\displaystyle x,y\in R}$ ${\displaystyle d(x,y)=d'(f(x),f(y))}$

Por ejemplo, dado el espacio semimétrico finito definido anteriormente, una incrustación isométrica desde a está definida por puntos , de modo que para todos . ${\displaystyle (R,d)}$ ${\displaystyle R}$ ${\displaystyle \mathbb {R} ^{k}}$ ${\textstyle A_{0},A_{1},\ldots ,A_{n}\in \mathbb {R} ^{k}}$ ${\displaystyle d(A_{i},A_{j})=d_{ij}}$ ${\displaystyle 0\leq i<j\leq n}$

Independencia afín

Dados los puntos , se definen como afínmente independientes , si no pueden caber dentro de un subespacio afín unidimensional de , para cualquiera , si el simplex que abarcan, tiene volumen positivo , es decir ,. ${\textstyle A_{0},A_{1},\ldots ,A_{n}\in \mathbb {R} ^{k}}$ ${\displaystyle l}$ ${\displaystyle \mathbb {R} ^{k}}$ ${\displaystyle \ell <n}$ ${\displaystyle n}$ ${\displaystyle v_{n}}$ ${\displaystyle n}$ ${\displaystyle \operatorname {Vol} _{n}(v_{n})>0}$

En general, cuando , son afínmente independientes, ya que un n -símplex 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 recta. 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. ${\displaystyle k\geq n}$

Cuando , deben ser afínmente dependientes. Esto se puede ver observando que cualquier -simplex que pueda caber dentro debe ser "plano". ${\displaystyle n>k}$ ${\displaystyle n}$ ${\displaystyle \mathbb {R} ^{k}}$

Determinantes de Cayley-Menger

Los determinantes de Cayley-Menger, que llevan el nombre de Arthur Cayley y Karl Menger, son determinantes de matrices de distancias entre conjuntos de puntos.

Sean n + 1  puntos en un espacio semimétrico, su determinante Cayley-Menger está definido por ${\textstyle A_{0},A_{1},\ldots ,A_{n}}$

${\displaystyle \operatorname {CM} (A_{0},\cdots ,A_{n})={\begin{vmatrix}0&d_{01}^{2}&d_{02}^{2}&\cdots &d_{0n}^{2}&1\\d_{01}^{2}&0&d_{12}^{2}&\cdots &d_{1n}^{2}&1\\d_{02}^{2}&d_{12}^{2}&0&\cdots &d_{2n}^{2}&1\\\vdots &\vdots &\vdots &\ddots &\vdots &\vdots \\d_{0n}^{2}&d_{1n}^{2}&d_{2n}^{2}&\cdots &0&1\\1&1&1&\cdots &1&0\end{vmatrix}}}$

Si , entonces constituyen los vértices de un n -simplex posiblemente degenerado en . Se puede demostrar que ^[6] el volumen n -dimensional del simplex satisface ${\textstyle A_{0},A_{1},\ldots ,A_{n}\in \mathbb {R} ^{k}}$ ${\displaystyle v_{n}}$ ${\displaystyle \mathbb {R} ^{k}}$ ${\displaystyle v_{n}}$

${\displaystyle \operatorname {Vol} _{n}(v_{n})^{2}={\frac {(-1)^{n+1}}{(n!)^{2}2^{n}}}\operatorname {CM} (A_{0},\ldots ,A_{n}).}$

Tenga en cuenta que, para el caso de , tenemos , lo que significa que el "volumen de dimensión 0" de un 0-símplex es 1, es decir, hay 1 punto en un 0-símplex. ${\displaystyle n=0}$ ${\displaystyle \operatorname {Vol} _{0}(v_{0})=1}$

${\textstyle A_{0},A_{1},\ldots ,A_{n}}$son afínmente independientes si , es decir . Por tanto, los determinantes de Cayley-Menger proporcionan una forma computacional de demostrar la independencia afín. ${\displaystyle \operatorname {Vol} _{n}(v_{n})>0}$ ${\displaystyle (-1)^{n+1}\operatorname {CM} (A_{0},\ldots ,A_{n})>0}$

Si , entonces los puntos deben ser afínmente dependientes, por lo tanto . El artículo de Cayley de 1841 estudió el caso especial de , es decir, cinco puntos cualesquiera en el espacio tridimensional deben tener . ${\displaystyle k<n}$ ${\displaystyle \operatorname {CM} (A_{0},\ldots ,A_{n})=0}$ ${\displaystyle k=3,n=4}$ ${\displaystyle A_{0},\ldots ,A_{4}}$ ${\displaystyle \operatorname {CM} (A_{0},\ldots ,A_{4})=0}$

Historia

El primer resultado en geometría de distancias es la fórmula de Herón , 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 del tetraedro a partir de las distancias entre sus 4 vértices.

La teoría moderna de la geometría a distancia comenzó con Arthur 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 isométricamente integrables en el espacio euclidiano de n dimensiones . ^{[9] [10]} En 1931, Menger utilizó relaciones de distancia para dar un tratamiento axiomático de la geometría euclidiana. ^[11] ${\displaystyle \mathbb {R} ^{n}}$

El libro de Leonard Blumenthal ^[12] ofrece una visión general de la geometría a distancia a nivel de posgrado, una gran parte del 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 isométricamente incrustable en el espacio euclidiano de dimensiones , pero no en for any , si y sólo si: ${\displaystyle (R,d)}$ ${\displaystyle n}$ ${\displaystyle \mathbb {R} ^{n}}$ ${\displaystyle \mathbb {R} ^{m}}$ ${\displaystyle 0\leq m<n}$

1. ${\displaystyle R}$contiene un subconjunto de puntos que es isométrico con un subconjunto de puntos afínmente independiente de ; ${\displaystyle (n+1)}$ ${\displaystyle S}$ ${\displaystyle (n+1)}$ ${\displaystyle \mathbb {R} ^{n}}$
2. cualquier subconjunto de puntos , obtenido sumando dos puntos adicionales cualesquiera de a , es congruente con un subconjunto de puntos de . ${\displaystyle (n+3)}$ ${\displaystyle S'}$ ${\displaystyle R}$ ${\displaystyle S}$ ${\displaystyle (n+3)}$ ${\displaystyle \mathbb {R} ^{n}}$

^{En [13]} se encuentra una demostración de este teorema en una forma ligeramente debilitada (para espacios métricos en lugar de espacios semimétricos).

Caracterización mediante determinantes de Cayley-Menger

Los siguientes resultados se prueban en el libro de Blumethal. ^[12]

Incrustar n + 1 puntos en los números reales

Dado un espacio semimétrico , con , y ,, una incrustación isométrica de en está definida por , tal que para todos . ${\displaystyle (S,d)}$ ${\displaystyle S=\{P_{0},\ldots ,P_{n}\}}$ ${\displaystyle d(P_{i},P_{j})=d_{ij}\geq 0}$ ${\displaystyle 0\leq i<j\leq n}$ ${\displaystyle (S,d)}$ ${\displaystyle \mathbb {R} ^{n}}$ ${\textstyle A_{0},A_{1},\ldots ,A_{n}\in \mathbb {R} ^{n}}$ ${\displaystyle d(A_{i},A_{j})=d_{ij}}$ ${\displaystyle 0\leq i<j\leq n}$

Una vez más, uno se pregunta si existe tal incrustación isométrica para . ${\displaystyle (S,d)}$

Una condición necesaria es fácil de ver: para todo , sea el k -simplex formado por , entonces ${\displaystyle k=1,\ldots ,n}$ ${\displaystyle v_{k}}$ ${\textstyle A_{0},A_{1},\ldots ,A_{k}}$

${\displaystyle (-1)^{k+1}\operatorname {CM} (P_{0},\ldots ,P_{k})=(-1)^{k+1}\operatorname {CM} (A_{0},\ldots ,A_{k})=2^{k}(k!)^{k}\operatorname {Vol} _{k}(v_{k})^{2}\geq 0}$

Lo contrario también se cumple. Es decir, si por todos , ${\displaystyle k=1,\ldots ,n}$

${\displaystyle (-1)^{k+1}\operatorname {CM} (P_{0},\ldots ,P_{k})\geq 0,}$

entonces tal incrustación existe.

Además, dicha incrustación es única hasta la isometría en . Es decir, dadas dos incrustaciones isométricas definidas por y , existe una isometría (no necesariamente única) , tal que para todos . Tal es único si y sólo si , es decir, son afínmente independientes. ${\displaystyle \mathbb {R} ^{n}}$ ${\displaystyle A_{0},A_{1},\ldots ,A_{n}}$ ${\displaystyle A'_{0},A'_{1},\ldots ,A'_{n}}$ ${\displaystyle T:\mathbb {R} ^{n}\to \mathbb {R} ^{n}}$ ${\displaystyle T(A_{k})=A'_{k}}$ ${\displaystyle k=0,\ldots ,n}$ ${\displaystyle T}$ ${\displaystyle \operatorname {CM} (P_{0},\ldots ,P_{n})\neq 0}$ ${\displaystyle A_{0},A_{1},\ldots ,A_{n}}$

Incrustar n + 2 y n + 3 puntos

Si los puntos se pueden incrustar en as , entonces, además de las condiciones anteriores, una condición adicional necesaria es que el -simplex formado por , no debe tener volumen -dimensional. Eso es, . ${\displaystyle n+2}$ ${\displaystyle P_{0},\ldots ,P_{n+1}}$ ${\displaystyle \mathbb {R} ^{n}}$ ${\displaystyle A_{0},\ldots ,A_{n+1}}$ ${\displaystyle (n+1)}$ ${\displaystyle A_{0},A_{1},\ldots ,A_{n+1}}$ ${\displaystyle (n+1)}$ ${\displaystyle \operatorname {CM} (P_{0},\ldots ,P_{n},P_{n+1})=0}$

Lo contrario también se cumple. Es decir, si por todos , ${\displaystyle k=1,\ldots ,n}$

${\displaystyle (-1)^{k+1}\operatorname {CM} (P_{0},\ldots ,P_{k})\geq 0,}$

y

${\displaystyle \operatorname {CM} (P_{0},\ldots ,P_{n},P_{n+1})=0,}$

entonces tal incrustación existe.

Para incrustar puntos en , las condiciones necesarias y suficientes son similares: ${\displaystyle n+3}$ ${\displaystyle \mathbb {R} ^{n}}$

1. Para todos , ; ${\displaystyle k=1,\ldots ,n}$ ${\displaystyle (-1)^{k+1}\operatorname {CM} (P_{0},\ldots ,P_{k})\geq 0}$
2. ${\displaystyle \operatorname {CM} (P_{0},\ldots ,P_{n},P_{n+1})=0;}$
3. ${\displaystyle \operatorname {CM} (P_{0},\ldots ,P_{n},P_{n+2})=0;}$
4. ${\displaystyle \operatorname {CM} (P_{0},\ldots ,P_{n},P_{n+1},P_{n+2})=0.}$

Incrustar arbitrariamente muchos puntos

El caso resulta suficiente en general. ${\displaystyle n+3}$

En general, dado un espacio semimétrico , se puede incrustar isométricamente si y sólo si existe , de modo que, para todos , y para cualquier , ${\displaystyle (R,d)}$ ${\displaystyle \mathbb {R} ^{n}}$ ${\displaystyle P_{0},\ldots ,P_{n}\in R}$ ${\displaystyle k=1,\ldots ,n}$ ${\displaystyle (-1)^{k+1}\operatorname {CM} (P_{0},\ldots ,P_{k})\geq 0}$ ${\displaystyle P_{n+1},P_{n+2}\in R}$

1. ${\displaystyle \operatorname {CM} (P_{0},\ldots ,P_{n},P_{n+1})=0;}$
2. ${\displaystyle \operatorname {CM} (P_{0},\ldots ,P_{n},P_{n+2})=0;}$
3. ${\displaystyle \operatorname {CM} (P_{0},\ldots ,P_{n},P_{n+1},P_{n+2})=0.}$

Y dicha incrustación es única hasta la isometría en . ${\displaystyle \mathbb {R} ^{n}}$

Además, si , entonces no se puede incrustar isométricamente en ningún . Y dicha incrustación es única hasta una isometría única en . ${\displaystyle \operatorname {CM} (P_{0},\ldots ,P_{n})\neq 0}$ ${\displaystyle \mathbb {R} ^{m},m<n}$ ${\displaystyle \mathbb {R} ^{n}}$

Por lo tanto, los determinantes de Cayley-Menger brindan una forma concreta de calcular si un espacio semimétrico puede ser incrustado en , para algún finito , y, de ser así, cuál es el mínimo . ${\displaystyle \mathbb {R} ^{n}}$ ${\displaystyle n}$ ${\displaystyle n}$

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 alcanzar el ancla.

Hay muchas aplicaciones en química. ^{[4] [12]} Técnicas como la RMN pueden medir distancias entre pares de átomos de una molécula determinada, 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 a grandes distancias en modelado macromolecular .
• Xplor-NIH. Basado en X-PLOR , para determinar la estructura de moléculas a partir de datos de experimentos de RMN. Resuelve problemas de geometría de distancia con métodos heurísticos (como el recocido simulado ) y métodos de búsqueda local (como la minimización de gradiente conjugado ).
• GITANO. Modelado y diseño molecular. Puede resolver problemas de geometría de distancia.
• Camarilla SNLSDP. 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 distancias euclidianas
• Escalado multidimensional (una técnica estadística utilizada cuando las distancias se miden con errores aleatorios)
• Espacio métrico
• La fórmula de Tartaglia
• Triangulación
• Trilateración

Referencias

1. Yemini, Y. (1978). "El problema del posicionamiento: borrador de un resumen intermedio". Conferencia sobre redes de sensores distribuidos, Pittsburgh .
2. 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. S2CID  15472897.
3. Mucherino, A.; Lavor, C.; Liberti, L.; Maculan, N. (2013). Geometría a distancia: teoría, métodos y aplicaciones.
4. Crippen, gerente general; Havel, TF (1988). Geometría a distancia y conformación molecular . John Wiley e hijos.
5. Biswas, P.; Lian, T.; Wang, T.; Ye, Y. (2006). "Algoritmos basados ​​en programación semidefinida para localización de redes de sensores". Transacciones ACM en redes de sensores . 2 (2): 188–220. doi :10.1145/1149283.1149286. S2CID  8002168.
6. "Volumenes simplex y el determinante Cayley-Menger". www.mathpages.com . Archivado desde el original el 16 de mayo de 2019 . Consultado el 8 de junio de 2019 .
7. Liberti, Leo; Lavor, Carlile (2016). "Seis joyas matemáticas de la historia de la geometría a distancia". Transacciones Internacionales en Investigación Operativa . 23 (5): 897–920. arXiv : 1502.02816 . doi :10.1111/itor.12170. ISSN  1475-3995. S2CID  17299562.
8. Cayley, Arturo (1841). "Sobre un teorema de la geometría de posición". Revista de Matemáticas de Cambridge . 2 : 267–271.
9. 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. S2CID  179178149.
10. Blumenthal, LM; Gillam, BE (1943). "Distribución de puntos en el espacio n". El Mensual Matemático Estadounidense . 50 (3): 181. doi : 10.2307/2302400. JSTOR  2302400.
11. Menger, Karl (1931). "Nueva base de la geometría euclidiana". Revista Estadounidense de Matemáticas . 53 (4): 721–745. doi :10.2307/2371222. ISSN  0002-9327. JSTOR  2371222.
12. Blumenthal, Leonard M. (1953). Teoría y Aplicaciones de la Geometría a Distancia . Prensa de la Universidad de Oxford.(2ª edición, Chelsea: 1970)
13. Bowers, John C.; Bowers, Philip L. (13 de diciembre de 2017). "A Menger Redux: incrustar espacios métricos isométricamente en el espacio euclidiano". El Mensual Matemático Estadounidense . 124 (7): 621. doi : 10.4169/amer.math.monthly.124.7.621. S2CID  50040864.