Geometría de distancias

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 forma más abstracta, es el estudio de los espacios semimétricos y las transformaciones isométricas entre ellos. Desde esta perspectiva, puede considerarse una disciplina dentro de la topología general . ^{[ 4 ]}

Históricamente, el primer resultado en geometría de distancias 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 , seguido de desarrollos más extensos en el siglo XX por Karl Menger y otros.

Los problemas de geometría de distancia 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

Los conceptos de geometría de la distancia se explicarán primero describiendo dos problemas particulares.

Primer problema: navegación hiperbólica

Consideremos tres estaciones de radio terrestres A, B, C, cuyas ubicaciones son conocidas. Un receptor de radio se encuentra en una ubicación desconocida. Los tiempos que tarda una señal de radio en viajar desde las estaciones hasta el receptor, $t_{A},t_{B},t_{C}$ , son desconocidos, pero las diferencias horarias, $t_{A}-t_{B}$ y $t_{A}-t_{C}$ , son conocidos. A partir de ellos, se conocen las diferencias de distancia. $c(t_{A}-t_{B})$ y $c(t_{A}-t_{C})$ , a partir de la cual se puede determinar la posición del receptor.

Segundo problema: reducción de dimensionalidad

En el análisis de datos , a menudo se proporciona una lista de datos representados como vectores. $\mathbf {v} =(x_{1},\ldots ,x_{n})\in \mathbb {R} ^{n}$ y es necesario determinar 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 el ahorro de espacio de almacenamiento y tiempo de cálculo, además de proporcionar una mejor comprensión de los datos.

Definiciones

Ahora formalizamos algunas definiciones que surgen naturalmente al considerar nuestros problemas.

Espacio semimétrico

Dado un listado de puntos en $R=\{P_{0},\ldots ,P_{n}\}$ , $n\geq 0$ , podemos especificar arbitrariamente las distancias entre pares de puntos mediante una lista de $d_{ij}>0$ , $0\leq i<j\leq n$ . 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. $R$ equipado con un semimétrico $d:R\times R\to [0,\infty )$ de tal manera que, para todos $x,y\in R$ ,

Positividad: $d(x,y)=0$ si y solo si $x=y$ .
Simetría: $d(x,y)=d(y,x)$ .

Cualquier espacio métrico es, con mayor razón, un espacio semimétrico. En particular, $\mathbb {R} ^{k}$ , el $k$ El espacio euclidiano de -dimensiones es el espacio métrico canónico en geometría de distancias.

La desigualdad triangular se omite en la definición porque no queremos imponer más restricciones a las distancias. $d_{ij}$ 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 $A,B,C$ en una línea, con $d_{AB}=1,d_{BC}=1,d_{AC}=2$ una medición inexacta podría dar $d_{AB}=0.99,d_{BC}=0.98,d_{AC}=2.00$ , violando la desigualdad triangular.

Incrustaciones isométricas

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

Por ejemplo, dado el espacio semimétrico finito $(R,d)$ definido anteriormente, una incrustación isométrica de $R$ a $\mathbb {R} ^{k}$ se define por puntos ${\textstyle A_{0},A_{1},\ldots ,A_{n}\in \mathbb {R} ^{k}}$ , de tal manera que $d(A_{i},A_{j})=d_{ij}$ a pesar de $0\leq i<j\leq n$ .

Independencia afín

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

En general, cuando $k\geq n$ Son afínmente independientes, ya que un n- símplex genérico no es degenerado. Por ejemplo, tres puntos en el plano, en general, no son colineales, porque el triángulo que forman no degenera en un segmento de línea . De manera similar, cuatro puntos en el espacio, en general, no son coplanares, porque el tetraedro que forman no degenera en un triángulo plano.

Cuando $n>k$ , deben ser dependientes por afinidad. Esto se puede ver al notar que cualquier $n$ -simplex que puede caber dentro $\mathbb {R} ^{k}$ debe ser "plano".

Determinantes de Cayley-Menger

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

Dejar ${\textstyle A_{0},A_{1},\ldots ,A_{n}}$ Sean n + 1 puntos en un espacio semimétrico, su determinante de Cayley-Menger se define por

\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 ${\textstyle A_{0},A_{1},\ldots ,A_{n}\in \mathbb {R} ^{k}}$ , entonces forman los vértices de un n -símplex posiblemente degenerado . $v_{n}$ en $\mathbb {R} ^{k}$ . Se puede demostrar que ^{[ 6 ]} el volumen n -dimensional del simplex $v_{n}$ Satisface

\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, en el caso de $n=0$ , tenemos $\operatorname {Vol} _{0}(v_{0})=1$ , lo que significa que el "volumen 0-dimensional" de un 0-símplex es 1, es decir, hay 1 punto en un 0-símplex.

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

Si $k<n$ , entonces los puntos deben ser afínmente dependientes, por lo tanto $\operatorname {CM} (A_{0},\ldots ,A_{n})=0$ El artículo de Cayley de 1841 estudió el caso especial de $k=3,n=4$ , es decir, cualesquiera cinco puntos $A_{0},\ldots ,A_{4}$ en el espacio tridimensional debe tener $\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 calcula el área de un triángulo a partir de las distancias entre sus tres 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., la generalizó para calcular el volumen de un tetraedro a partir de las distancias entre sus cuatro 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 incrustables en el espacio euclidiano n -dimensional . $\mathbb {R} ^{n}$ . ^{[ 9 ]}^{[ 10 ]} En 1931, Menger utilizó relaciones de distancia para dar un tratamiento axiomático de la geometría euclidiana. ^{[ 11 ]}

El libro de Leonard Blumenthal ^{[ 12 ]} ofrece una visió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 $(R,d)$ es isométricamente integrable en el $n$ espacio euclidiano de -dimensiones $\mathbb {R} ^{n}$ , pero no en $\mathbb {R} ^{m}$ para cualquier $0\leq m<n$ , si y solo si:
$R$ contiene un $(n+1)$ subconjunto de puntos $S$ que es isométrico con una afinidad independiente $(n+1)$ -subconjunto de puntos de $\mathbb {R} ^{n}$ ;
cualquier $(n+3)$ subconjunto de puntos $S'$ , obtenido al sumar cualesquiera dos puntos adicionales de $R$ a $S$ , es congruente con un $(n+3)$ -subconjunto de puntos de $\mathbb {R} ^{n}$ .

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

Caracterización mediante determinantes de Cayley-Menger

Los siguientes resultados se demuestran en el libro de Blumethal. ^{[ 12 ]}

Incrustar n + 1 puntos en los números reales

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

Nuevamente, cabe preguntarse si existe tal incrustación isométrica para $(S,d)$ .

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

(-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 es cierto. Es decir, si para todo $k=1,\ldots ,n$ ,

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

entonces existe tal incrustación.

Además, dicha incrustación es única salvo isometría en $\mathbb {R} ^{n}$ . Es decir, dados dos incrustaciones isométricas cualesquiera definidas por $A_{0},A_{1},\ldots ,A_{n}$ , y $A'_{0},A'_{1},\ldots ,A'_{n}$ , existe una isometría (no necesariamente única) $T:\mathbb {R} ^{n}\to \mathbb {R} ^{n}$ , de tal manera que $T(A_{k})=A'_{k}$ a pesar de $k=0,\ldots ,n$ . Semejante $T$ es único si y solo si $\operatorname {CM} (P_{0},\ldots ,P_{n})\neq 0$ , eso es, $A_{0},A_{1},\ldots ,A_{n}$ son afínmente independientes.

Incrustar n + 2 y n + 3 puntos

Si $n+2$ agujas $P_{0},\ldots ,P_{n+1}$ puede estar incrustado en $\mathbb {R} ^{n}$ como $A_{0},\ldots ,A_{n+1}$ , entonces, además de las condiciones anteriores, una condición necesaria adicional es que la $(n+1)$ -símplex formado por $A_{0},A_{1},\ldots ,A_{n+1}$ , no debe tener $(n+1)$ Volumen -dimensional. Es decir, $\operatorname {CM} (P_{0},\ldots ,P_{n},P_{n+1})=0$ .

Lo contrario también es cierto. Es decir, si para todo $k=1,\ldots ,n$ ,

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

y

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

entonces existe tal incrustación.

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

A pesar de $k=1,\ldots ,n$ , $(-1)^{k+1}\operatorname {CM} (P_{0},\ldots ,P_{k})\geq 0$ ;
$\operatorname {CM} (P_{0},\ldots ,P_{n},P_{n+1})=0;$
$\operatorname {CM} (P_{0},\ldots ,P_{n},P_{n+2})=0;$
$\operatorname {CM} (P_{0},\ldots ,P_{n},P_{n+1},P_{n+2})=0.$

Incrustar arbitrariamente muchos puntos

El $n+3$ El caso resulta ser suficiente en general.

En general, dado un espacio semimétrico $(R,d)$ , puede incrustarse isométricamente en $\mathbb {R} ^{n}$ si y solo si existe $P_{0},\ldots ,P_{n}\in R$ , de tal manera que, para todo $k=1,\ldots ,n$ , $(-1)^{k+1}\operatorname {CM} (P_{0},\ldots ,P_{k})\geq 0$ y para cualquier $P_{n+1},P_{n+2}\in R$ ,

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

Y tal incrustación es única salvo isometría en $\mathbb {R} ^{n}$ .

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

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

Aplicaciones

Existen muchas aplicaciones de la geometría de distancias. ^{[ 3 ]}

En redes de telecomunicaciones como el GPS , se conocen las posiciones de algunos sensores (llamados anclas) y también algunas de las distancias entre ellos: el problema consiste en 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 distancias para localizar barcos basándose en el 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 , determina 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 del gradiente conjugado ).
TINKER . Modelado y diseño molecular. Puede resolver problemas de geometría de distancias.
SNLSDPclique . Código MATLAB para localizar sensores en una red de sensores en función de las distancias entre ellos.

Véase también

matriz de distancia euclidiana
Escalamiento 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

↑ Yemini, Y. (1978). "El problema del posicionamiento: un borrador de un resumen intermedio". Conferencia sobre redes de sensores distribuidos, Pittsburgh .
1 2 Liberti, Leo; Lavor, Carlile; MacUlan, Nelson; Mucherino, Antonio (2014). "Geometría de la distancia euclidiana y aplicaciones". SIAM Review . 56 : 3– 69. arXiv : 1205.0349 . doi : 10.1137/120875909 . S2CID 15472897 .
1 2 Mucherino, A.; Lavor, C.; Liberti, L.; Maculan, N. (2013). Geometría de distancias: teoría, métodos y aplicaciones .
1 2 3 Crippen, GM; Havel, TF (1988). Geometría de distancias y conformación molecular . John Wiley & Sons.
1 2 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 .
↑ "Volúmenes simplex y el determinante de Cayley-Menger" . www.mathpages.com . Archivado del original el 16 de mayo de 2019. Consultado el 8 de junio de 2019 .
↑ Liberti, Leo; Lavor, Carlile (2016). "Seis joyas matemáticas de la historia de la geometría de la distancia". International Transactions in Operational Research . 23 (5): 897– 920. arXiv : 1502.02816 . doi : 10.1111/itor.12170 . ISSN 1475-3995 . S2CID 17299562 .
↑ Cayley, Arthur (1841). "Sobre un teorema en la geometría de la posición". Cambridge Mathematical Journal . 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 . S2CID 179178149 .
↑ 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 .
↑ Menger, Karl (1931). "Nuevos fundamentos de la geometría euclidiana". American Journal of Mathematics . 53 (4): 721– 745. doi : 10.2307/2371222 . ISSN 0002-9327 . JSTOR 2371222 .
1 2 3 Blumenthal, Leonard M. (1953). Teoría y aplicaciones de la geometría de distancias . Oxford University Press.( 2ª edición , Chelsea: 1970)
↑ Bowers, John C.; Bowers, Philip L. (13 de diciembre de 2017). "Una revisión de Menger: Incrustaciones isométricas de espacios métricos en el espacio euclidiano". The American Mathematical Monthly . 124 (7): 621. doi : 10.4169/amer.math.monthly.124.7.621 . S2CID 50040864 .

[positioning-1] Yemini, Y. (1978). "El problema del posicionamiento: un borrador de un resumen intermedio". Conferencia sobre redes de sensores distribuidos, Pittsburgh .

[siam-2] 1 2 Liberti, Leo; Lavor, Carlile; MacUlan, Nelson; Mucherino, Antonio (2014). "Geometría de la distancia euclidiana y aplicaciones". SIAM Review . 56 : 3– 69. arXiv : 1205.0349 . doi : 10.1137/120875909 . S2CID 15472897 .

[DGAbook-3] 1 2 Mucherino, A.; Lavor, C.; Liberti, L.; Maculan, N. (2013). Geometría de distancias: teoría, métodos y aplicaciones .

[crippen-4] 1 2 3 Crippen, GM; Havel, TF (1988). Geometría de distancias y conformación molecular . John Wiley & Sons.

[sensors-5] 1 2 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 el determinante de Cayley-Menger" . www.mathpages.com . Archivado del 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 la distancia". International Transactions in Operational Research . 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 .

[:0-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). "Nuevos fundamentos de la geometría euclidiana". American Journal of Mathematics . 53 (4): 721– 745. doi : 10.2307/2371222 . ISSN 0002-9327 . JSTOR 2371222 .

[blumenthal-12] 1 2 3 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 revisión de Menger: Incrustaciones isométricas de espacios métricos en el espacio euclidiano". The American Mathematical Monthly . 124 (7): 621. doi : 10.4169/amer.math.monthly.124.7.621 . S2CID 50040864 .

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 11 ]

[ 12 ]

[ 13 ] .