Marco geométrico

La llave geométrica o el gráfico t-spanning, o el gráfico t - spanning , se introdujo originalmente como un gráfico ponderado en un conjunto de puntos como vértices, para los cuales hay un camino t entre cualquier par de vértices para un parámetro fijo t . Una ruta t se define como una ruta en un gráfico con un peso que no excede t veces la distancia espacial entre los puntos finales. El parámetro t se denomina factor de estiramiento esqueleto [1] .

En geometría computacional, el concepto fue discutido por primera vez por L.P. Chu en 1986 [2] , aunque el término "spanner" (esqueleto) no se menciona en el artículo.

El concepto de árboles de expansión se conoce en la teoría de grafos - t - esqueletos, estos son subgrafos de expansión de gráficos con propiedades de estiramiento similares, donde la distancia entre los vértices del gráfico se define en términos de teoría de grafos. Por tanto, los árboles de expansión geométricos son árboles de expansión de grafos completos incrustados en el plano , en los que los pesos de las aristas son iguales a las distancias entre los vértices en la métrica correspondiente.

Los esqueletos se pueden usar en geometría computacional para resolver algunos problemas de proximidad . También encuentran aplicaciones en otras áreas como la planificación del tráfico , redes de comunicación - fiabilidad de la red, optimización del roaming en redes móviles , etc.

Varias columnas vertebrales y medidas de calidad

Hay varias medidas utilizadas para analizar la calidad de los núcleos. Las medidas más comunes son el número de aristas, el peso total y el grado máximo de los vértices. Los valores asintóticamente óptimos para estas medidas son los bordes, el peso total y el grado máximo (donde MST significa el peso del árbol de expansión mínimo ). $En)$ ${\ estilo de visualización O (MST)}$ $O(1)$

Se sabe que encontrar un árbol de expansión en el plano euclidiano con un estiramiento mínimo en n puntos con m aristas como máximo es un problema NP-difícil [3] .

Hay muchos algoritmos que funcionan bien bajo varias medidas de calidad. Los algoritmos rápidos incluyen la descomposición de pares bien separados ( ) y los gráficos theta , que construyen extensiones con un número lineal de aristas en el tiempo . Si se requieren mejores pesos y grados de vértice, la expansión codiciosa se calcula en tiempo casi cuadrático. $O(n\log n)$

Gráfico theta

Theta-graph o -graph pertenece a la familia de spannings basados en un cono. El principal método de construcción es dividir el espacio alrededor de cada vértice en muchos conos (un cono plano son dos rayos, es decir, un ángulo) que separan los vértices restantes del gráfico. Al igual que los gráficos de Yao , el gráfico - contiene como máximo una arista para un cono. El enfoque difiere en la forma en que se seleccionan los bordes. Mientras que los gráficos de Yao eligen el vértice más cercano de acuerdo con la distancia métrica en el gráfico, el gráfico determina un rayo fijo contenido en cada cono (generalmente la bisectriz del cono) y elige los vecinos más cercanos (es decir, aquellos que tienen la menor distancia al rayo) . $\Theta$ $\Theta$ $\Theta$

Esqueleto codicioso

Un árbol de expansión codicioso o un gráfico codicioso se define como un gráfico obtenido al agregar repetidamente un borde entre puntos que no tienen una ruta t . Los algoritmos para calcular este gráfico se conocen como algoritmos de expansión codiciosos. Se sigue trivialmente de la construcción que los grafos codiciosos son t -esqueletos.

El núcleo codicioso fue descubierto de forma independiente en 1989 por Althöfer [4] y Bern (inédito).

El esqueleto codicioso logra el número asintóticamente óptimo de aristas, el peso total y el grado máximo de vértice, y proporciona los mejores valores de medida en la práctica. Se puede construir en el tiempo usando el espacio [5] . $O(n^{2}\log n)$ $O(n^{2})$

Triangulación de Delaunay

El principal resultado de Chu fue que, para un conjunto de puntos en un plano, existe una triangulación de estos conjuntos de puntos, de modo que para dos puntos cualesquiera, existe un camino a lo largo de los bordes de la triangulación con una longitud que no excede la distancia euclidiana entre los dos puntos. . El resultado se utilizó en la planificación del tráfico para encontrar una aproximación aceptable del camino más corto entre los obstáculos. ${\ estilo de pantalla \ estilo de script {\ sqrt {1}} 0}$

El límite superior más conocido para una triangulación de Delaunay es el esqueleto de sus vértices [6] . El límite inferior se ha incrementado de a 1.5846 [7] . $\scriptstyle {(4{\sqrt {3}}/9)\pi }\aproximadamente 2{,}418$ ${\ estilo de pantalla \ estilo de script {{\ pi}/2}}$

Una descomposición bien separada de pares

El esqueleto se puede construir a partir de una descomposición completamente separada de pares de la siguiente manera. Construimos un gráfico con un conjunto de puntos como vértices y para cada par en WSPD agregamos un borde desde un punto arbitrario a un punto arbitrario . Tenga en cuenta que el gráfico resultante tiene un número lineal de aristas, ya que WSPD tiene un número lineal de pares [8] . $S$ ${\ estilo de visualización \ {A, B \}}$ $a \ en A$ $b\en B$

Prueba de la corrección del algoritmo [9]
Necesitamos estas dos propiedades WSPD Lema 1 : Sea una descomposición de pares completamente separada con respecto a . Sea y . entonces _ ${\ estilo de visualización \ {A, B \}}$ $s$ ${\ estilo de visualización p, p' \ en A}$ ${\ estilo de visualización q \ en B}$ $\|pp'\|\leqslant (2/s)\|pq\|$ Lema 2 : Sea una descomposición de pares completamente separada con respecto a . Sea y . Entonces, . ${\ estilo de visualización \ {A, B \}}$ $s$ ${\ estilo de visualización p, p' \ en A}$ ${\ estilo de visualización q, q' \ en B}$ $\|p'q'\|\leqslant (1+4/s)\|pq\|$ Sea una descomposición bien separada de pares con respecto a en WSPD. Sea una arista conectando con . Que haya un punto y un punto . Según la definición de WSPD, basta con comprobar que existe una ruta -backbone, o -path para abreviar, entre y , que denotamos por . Denotemos la longitud del camino por . ${\ estilo de visualización \ {A, B \}}$ $s$ $[a,b]$ $A$ $B$ ${\ estilo de visualización p \ en A}$ ${\ estilo de visualización q \ en B}$ $t$ $t$ $pags$ $q$ ${\ Displaystyle P_ {pq}}$ ${\ Displaystyle P_ {pq}}$ $\|P_{pq}\|$ Suponga que hay un camino entre cualquier par de puntos con una distancia menor o igual que y . De la desigualdad del triángulo, supuestos, y el hecho de que, y según el Lema 1, tenemos: $t$ ${\ estilo de visualización \| pq \|}$ ${\ estilo de visualización s> 2}$ $\|pa\|\leqslant (2/s)\|pq\|\Rightarrow \|pa\|<\|pq\|$ $\|bq\|\leqslant (2/s)\|pq\|\Rightarrow \|bq\|<\|pq\|$ $\|P_{pq}\|\leqslant t\|pa\|+\|ab\|+t\|bq\|$ Del Lema 1 y 2 obtenemos: ${\begin{alineado}\|P_{pq}\|&\leqslant t(2/s)\|pq\|+(1+4/s)\|pq\|+t(2/s)\|pq\|\\ &=t(4/s)\|pq\|+(1+4/s)\|pq\|\\&=\left({\frac {4t+4}{s}}\right)\|pq\|+\|pq \|\\&=\left({\frac {4(t+1)}{s}}+1\right)\|pq\|\end{alineado}}$ De modo que: ${\begin{alineado}t&={\frac {4(t+1)}{s}}+1\\t-1&={\frac {4(t+1)}{s}}\ \s(t-1)&=4(t+1)\\s(t-1)-4(t+1)&=0\\st-s-4t-4&=0\\t(s- 4)-s-4&=0\\t(s-4)&=s+4\\t&={\frac {s+4}{s-4}}\end{alineado}}$ Y así, si y , entonces tenemos un esqueleto para el conjunto de puntos . ${\ estilo de visualización t = (s+4)/(s-4)}$ ${\ estilo de visualización> 4}$ $t$ $S$

Prueba de la corrección del algoritmo [9]

Necesitamos estas dos propiedades WSPD

Lema 1 : Sea una descomposición de pares completamente separada con respecto a . Sea y . entonces _ ${\ estilo de visualización \ {A, B \}}$ $s$ ${\ estilo de visualización p, p' \ en A}$ ${\ estilo de visualización q \ en B}$ $|pp'|\leqslant (2/s)|pq|$

Lema 2 : Sea una descomposición de pares completamente separada con respecto a . Sea y . Entonces, . ${\ estilo de visualización \ {A, B \}}$ $s$ ${\ estilo de visualización p, p' \ en A}$ ${\ estilo de visualización q, q' \ en B}$ $|p'q'|\leqslant (1+4/s)|pq|$

Sea una descomposición bien separada de pares con respecto a en WSPD. Sea una arista conectando con . Que haya un punto y un punto . Según la definición de WSPD, basta con comprobar que existe una ruta -backbone, o -path para abreviar, entre y , que denotamos por . Denotemos la longitud del camino por . ${\ estilo de visualización \ {A, B \}}$ $s$ $[a,b]$ $A$ $B$ ${\ estilo de visualización p \ en A}$ ${\ estilo de visualización q \ en B}$ $t$ $t$ $pags$ $q$ ${\ Displaystyle P_ {pq}}$ ${\ Displaystyle P_ {pq}}$ $|P_{pq}|$

Suponga que hay un camino entre cualquier par de puntos con una distancia menor o igual que y . De la desigualdad del triángulo, supuestos, y el hecho de que, y según el Lema 1, tenemos: $t$ ${\ estilo de visualización | pq |}$ ${\ estilo de visualización s> 2}$ $|pa|\leqslant (2/s)|pq|\Rightarrow |pa|<|pq|$ $|bq|\leqslant (2/s)|pq|\Rightarrow |bq|<|pq|$

$|P_{pq}|\leqslant t|pa|+|ab|+t|bq|$

Del Lema 1 y 2 obtenemos:

${\begin{alineado}|P_{pq}|&\leqslant t(2/s)|pq|+(1+4/s)|pq|+t(2/s)|pq|\\ &=t(4/s)|pq|+(1+4/s)|pq|\\&=\left({\frac {4t+4}{s}}\right)|pq|+|pq |\\&=\left({\frac {4(t+1)}{s}}+1\right)|pq|\end{alineado}}$

De modo que:

${\begin{alineado}t&={\frac {4(t+1)}{s}}+1\\t-1&={\frac {4(t+1)}{s}}\ \s(t-1)&=4(t+1)\\s(t-1)-4(t+1)&=0\\st-s-4t-4&=0\\t(s- 4)-s-4&=0\\t(s-4)&=s+4\\t&={\frac {s+4}{s-4}}\end{alineado}}$

Y así, si y , entonces tenemos un esqueleto para el conjunto de puntos . ${\ estilo de visualización t = (s+4)/(s-4)}$ ${\ estilo de visualización> 4}$ $t$ $S$

De acuerdo con la prueba, uno puede tener un valor arbitrario para expresando from , lo que da . $t$ $s$ ${\ estilo de visualización t = (s+4)/(s-4)}$ ${\ estilo de visualización s = 4 (t + 1)/(t-1)}$

Notas

↑ Narasimhan, Smid, 2007 .
↑ Chew, 1986 , pág. 169–177.
↑ Klein y Kutz, 2007 , pág. 196–207.
↑ Althöfer, Das, Dobkin, Joseph, Soares, 1993 , p. 81–100.
↑ Bose, Carmi, Farshi, Maheshwari, Smid, 2010 , pág. 711–729.
↑ Keil y Gutwin 1992 , pág. 13–28.
↑ Bose, Devroye, Loeffler, Snoeyink, Verma, 2009 , pág. 165–167.
↑ Callahan, Kosaraju, 1995 , pág. 67–90.
↑ Callahan, Kosaraju, 1993 , pág. 291–300.

Literatura

L. Paul masticar. Hay un gráfico plano casi tan bueno como el gráfico completo // Proc. 2do Simposio Anual de Geometría Computacional. - 1986. - doi : 10.1145/10515.10534 .
Rolf Klein, Martín Kutz. Calcular gráficos de dilatación mínima geométrica es NP-Hard // Proc. XIV Simposio Internacional de Dibujo Gráfico , Karlsruhe, Alemania, 2006 / Michael Kaufmann, Dorothea Wagner. - Springer Verlag , 2007. - T. 4372. - ( Lecture Notes in Computer Science ). — ISBN 978-3-540-70903-9 . -doi : 10.1007 / 978-3-540-70904-6 .
Paul B. Callahan, S. Rao Kosaraju. Algoritmos más rápidos para algunos problemas de gráficos geométricos en dimensiones superiores // Actas del cuarto simposio anual ACM-SIAM sobre algoritmos discretos . - Austin, Texas, EE.UU.: Sociedad de Matemáticas Industriales y Aplicadas, 1993. - (SODA '93). - ISBN 0-89871-313-7 . -doi : 10.1145/ 313559.313777 .
Althöfer I., Das G., Dobkin DP, Joseph D., Soares J. Sobre llaves inglesas dispersas de gráficos ponderados. // Geometría Discreta y Computacional. - 1993. - T. 9 . -doi : 10.1007/ bf02189308 .
Bose P., Carmi P., Farshi M., Maheshwari A., Smid. M. Cálculo de la llave inglesa codiciosa en tiempo casi cuadrático // Algorithmica. - 2010. - T. 58 . -doi : 10.1007/ s00453-009-9293-4 .
Keil JM, Gutwin CA Clases de gráficos que aproximan el gráfico euclidiano completo // Geometría discreta y computacional . - 1992. - T. 7 , nº. 1 . -doi : 10.1007/ BF02187821 .
Prosenjit Bose, Luc Devroye, Maarten Loeffler, Jack Snoeyink, Vishal Verma. La relación de expansión de la triangulación de Delaunay es mayor que ${\ estilo de pantalla \ estilo de script {\ pi /2}}$ // Conferencia Canadiense sobre Geometría Computacional . —Vancouver, 2009.
Callahan PB, Kosaraju SR Una descomposición de conjuntos de puntos multidimensionales con aplicaciones a k-vecinos más cercanos y campos de potencial de n-cuerpo // Journal of the ACM. - 1995. - Enero ( vol. 42 , número 1 ). doi : 10.1145 / 200836.200853 .
Giri Narasimhan, Michiel Smid. Redes geométricas de llave inglesa . - Prensa de la Universidad de Cambridge , 2007. - ISBN 0-521-81513-4 .