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 los espacios semimétricos y las transformaciones isométricas entre ellos. Desde este punto de vista, puede considerarse como una materia dentro de la topología general . ^[4]

Históricamente, el primer resultado en geometría de distancias es la fórmula de Herón del siglo I d. C. La teoría moderna comenzó en el siglo XIX con el trabajo de Arthur Cayley , seguido por desarrollos más amplios en el siglo XX por Karl Menger y otros.

Los problemas de geometría de distancias surgen siempre que 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

Primero se explicarán los conceptos de geometría de distancias describiendo dos problemas particulares.

Problema de la navegación hiperbólica

Primer problema:Navegación hiperbólica

Consideremos tres estaciones de radio terrestres A, B, C, cuyas ubicaciones son conocidas. Un receptor de radio está en una ubicación desconocida. Los tiempos que tarda una señal de radio en viajar desde las estaciones hasta el receptor, , son desconocidos, pero las diferencias de tiempo, y , son conocidas. A partir de ellas, se conocen las diferencias de distancia y , desde las que 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 dimensión

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 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 . ${\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 una semimétrica 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)}$

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

La desigualdad triangular 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 línea, 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}$

Incrustaciones isométricas

Dados dos espacios semimétricos, , una incrustación isométrica de a es una función que preserva la semimétrica, es decir, para todo , . ${\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 de a está definida por los puntos , tal que para todo . ${\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 y solo si no pueden caber dentro de un subespacio afín unidimensional de , para cualquier , si y solo si el - símplex 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 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. ${\displaystyle k\geq n}$

Cuando , deben ser dependientes por afinidad. Esto se puede ver al notar que cualquier -símplex 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, llamados así en honor a 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 de 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 forman los vértices de un n -símplex posiblemente degenerado en . Se puede demostrar que ^[6] el volumen n -dimensional del símplex 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}).}$

Nótese 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 y solo si , es decir, . Por lo tanto, los determinantes de Cayley-Menger brindan 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, cualesquiera cinco puntos 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 los cuadriláteros cíclicos . Tartaglia , del siglo XVI d.C., la generaliza para dar el volumen del tetraedro a partir de las distancias entre sus 4 vértices.

La teoría moderna de la geometría de distancias 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 encajables en el espacio euclidiano n -dimensional . ^{[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 descripción general de la geometría de distancias 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 isométricamente integrable en el espacio euclidiano -dimensional , pero no en ningún espacio , 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 al sumar dos puntos adicionales 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}}$

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

Caracterización a través de determinantes de Cayley-Menger

Los siguientes resultados están demostrados en el libro de Blumethal. ^[12]

Incrustarnorte+ 1 punto 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 todo . ${\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}$

De nuevo, 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 -símplex 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}$

También se cumple lo contrario, es decir, si para todos , ${\displaystyle k=1,\ldots ,n}$

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

Entonces existe tal incrustación.

Además, dicha 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 los . Tal es única si y solo 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}}$

Incrustarnorte+ 2 ynorte+ 3 puntos

Si se pueden incrustar puntos en como , entonces, además de las condiciones anteriores, una condición necesaria adicional es que el -símplex formado por , no debe tener un volumen -dimensional. Es decir, . ${\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}$

También se cumple lo contrario, es decir, si para 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 existe tal incrustación.

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.}$

Incorporar tantos puntos como se desee

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

En general, dado un espacio semimétrico , se puede incrustar isométricamente en si y solo si existe , tal que, para todo , , 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 que haya 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 proporcionan una forma concreta de calcular si un espacio semimétrico puede estar incluido en , para algún , finito , y si es así, cuál es el . ${\displaystyle \mathbb {R} ^{n}}$ ${\displaystyle n}$ ${\displaystyle n}$

Aplicaciones

La geometría de la distancia tiene muchas aplicaciones. ^[3]

En redes de telecomunicaciones como el GPS , se conocen las posiciones de algunos sensores (que se denominan 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 la geometría de la 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 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 distancias con métodos heurísticos (como el recocido simulado ) y métodos de búsqueda local (como la minimización de gradiente conjugado ).
• TINKER. Modelado y diseño molecular. Puede resolver problemas de geometría de distancias.
• SNLSDPclique. Código MATLAB para ubicar sensores en una red de sensores en función de las distancias entre ellos.

Véase también

• Matriz de distancia euclidiana
• Escalamiento multidimensional (técnica estadística utilizada cuando se miden distancias 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). "Geometría de distancias euclidianas y aplicaciones". SIAM Review . 56 : 3–69. arXiv : 1205.0349 . doi :10.1137/120875909. S2CID  15472897.
3. Mucherino, A.; Lavor, C.; Liberti, L.; Maculan, N. (2013). Geometría de distancias: teoría, métodos y aplicaciones.
4. Crippen, GM; Havel, TF (1988). Geometría de distancias y conformación molecular . John Wiley & Sons.
5. Biswas, P.; Lian, T.; Wang, T.; Ye, Y. (2006). "Algoritmos basados ​​en programación semidefinida para la localización de redes de sensores". ACM Transactions on Sensor Networks . 2 (2): 188–220. doi :10.1145/1149283.1149286. S2CID  8002168.
6. "Volúmenes simplex y determinante de 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 de distancias". 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, Arthur (1841). "Sobre un teorema en la geometría de la posición". Cambridge Mathematical Journal . 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". The American Mathematical Monthly . 50 (3): 181. doi :10.2307/2302400. JSTOR  2302400.
11. Menger, Karl (1931). "Nueva base de la geometría euclidiana". American Journal of Mathematics . 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 de distancias . Oxford University Press.(2ª edición, Chelsea: 1970)
13. Bowers, John C.; Bowers, Philip L. (13 de diciembre de 2017). "Una versión redux de Menger: 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.