Gráfico Theta

En geometría computacional , el gráfico Theta , o${\displaystyle \Theta }$-grafo , es un tipo de grafo de expansión geométrica similar a un grafo de Yao . El método básico de construcción implica particionar el espacio alrededor de cada vértice en un conjunto de conos , que a su vez particionan los vértices restantes del grafo. Al igual que los grafos de Yao, un${\displaystyle \Theta }$-El grafo contiene como máximo una arista por cono; donde difieren es en cómo se selecciona esa arista. Mientras que los grafos Yao seleccionarán el vértice más cercano de acuerdo con el espacio métrico del grafo, el${\displaystyle \Theta }$-El grafo define un rayo fijo contenido dentro de cada cono (convencionalmente la bisectriz del cono) y selecciona el vecino más cercano con respecto a las proyecciones ortogonales a ese rayo. El grafo resultante exhibe varias buenas propiedades de expansión. ^{[ 1 ]}

${\displaystyle \Theta }$Los gráficos fueron descritos por primera vez por Clarkson ^{[ 2 ]} en 1987 e independientemente por Keil ^{[ 3 ]} en 1988.

${\displaystyle \Theta }$Los gráficos se especifican con algunos parámetros que determinan su construcción. El parámetro más obvio es${\displaystyle k}$, que corresponde al número de conos de ángulo igual que dividen el espacio alrededor de cada vértice. En particular, para un vértice${\displaystyle p}$, un cono de aproximadamente${\displaystyle p}$puede imaginarse como dos rayos infinitos que emanan de él con un ángulo${\displaystyle \theta =2\pi /k}$entre ellos. Con respecto a${\displaystyle p}$, podemos etiquetar estos conos como${\displaystyle C_{1}}$a través de${\displaystyle C_{k}}$en un patrón en sentido contrario a las agujas del reloj desde${\displaystyle C_{1}}$, que convencionalmente se abre de manera que su bisectriz tenga un ángulo 0 con respecto al plano. Como estos conos particionan el plano, también particionan el conjunto de vértices restante del grafo (suponiendo una posición general ) en los conjuntos${\displaystyle V_{1}}$a través de${\displaystyle V_{k}}$, nuevamente con respecto a${\displaystyle p}$. Cada vértice del gráfico obtiene el mismo número de conos en la misma orientación, y podemos considerar el conjunto de vértices que caen en cada uno.

Considerando un solo cono, necesitamos especificar otro rayo que emana de${\displaystyle p}$, que etiquetaremos${\displaystyle l}$. Para cada vértice en${\displaystyle V_{i}}$, consideramos la proyección ortogonal de cada${\displaystyle v\in V_{i}}$sobre${\displaystyle l}$. Supongamos que${\displaystyle r}$es el vértice con la proyección más cercana de este tipo, entonces la arista${\displaystyle \{p,r\}}$se agrega al grafo. Esta es la principal diferencia con los grafos Yao, que siempre seleccionan el vértice más cercano; en la imagen de ejemplo, un grafo Yao incluiría la arista.${\displaystyle \{p,q\}}$en cambio.

Construcción de un${\displaystyle \Theta }$-es posible graficar con un algoritmo de barrido lineal en${\displaystyle O(n\log {n})}$tiempo. ^{[ 1 ]}

${\displaystyle \Theta }$Los gráficos exhiben varias propiedades geométricas útiles de tipo "expansor" .

Cuando el parámetro${\displaystyle k}$es una constante, la${\displaystyle \Theta }$-graph es un expansor disperso. Como cada cono genera como máximo una arista por cono, la mayoría de los vértices tendrán un grado pequeño, y el grafo general tendrá como máximo${\displaystyle k\cdot n=O(n)}$bordes.

El factor de estiramiento entre cualquier par de puntos en un conector se define como la razón entre su distancia en el espacio métrico y su distancia dentro del conector (es decir, desde los bordes siguientes del conector). El factor de estiramiento de todo el conector es el factor de estiramiento máximo sobre todos los pares de puntos dentro del mismo. Recordemos que anteriormente...${\displaystyle \theta =2\pi /k}$, entonces cuando${\displaystyle k\geq 9}$, el${\displaystyle \Theta }$-El gráfico tiene un factor de estiramiento de como máximo${\displaystyle 1/(\cos \theta -\sin \theta )}$. ^{[ 1 ]} Si la línea de proyección ortogonal${\displaystyle l}$en cada cono se elige como bisectriz, entonces para${\displaystyle k\geq 7}$, la relación de expansión es como máximo${\displaystyle 1/(1-2\sin(\pi /k))}$. ^{[ 4 ]}

Para${\displaystyle k=1}$, el${\displaystyle \Theta }$-el gráfico forma un gráfico de vecinos más cercanos . Para${\displaystyle k=2}$Es fácil ver que el grafo está conectado, ya que cada vértice se conectará con algo a su izquierda y con algo a su derecha, si existen.${\displaystyle k=3}$^{[ 5 ]} ,${\displaystyle 4}$^{[ 6 ]}${\displaystyle 5}$, ^{[ 7 ]}${\displaystyle 6}$, ^{[ 8 ]} y${\displaystyle \geq 7}$, ^{[ 4 ]} el${\displaystyle \Theta }$Se sabe que el grafo es conexo. Muchos de estos resultados también proporcionan cotas superiores y/o inferiores para sus razones de expansión.

Cuando${\displaystyle k}$es un número par , podemos crear una variante del${\displaystyle \Theta _{k}}$-gráfico conocido como la mitad-${\displaystyle \Theta _{k}}$-grafo , donde los conos mismos se dividen en conjuntos pares e impares de forma alternada, y las aristas solo se consideran en los conos pares (o, solo en los conos impares). Medio-${\displaystyle \Theta _{k}}$Se sabe que los gráficos tienen algunas propiedades muy agradables por sí mismos. Por ejemplo, la mitad-${\displaystyle \Theta _{6}}$-gráfico (y, en consecuencia, el${\displaystyle \Theta _{6}}$-gráfico, que es simplemente la unión de dos semigráficos complementarios-${\displaystyle \Theta _{6}}$-grafos) se sabe que es un 2-spanner. ^{[ 8 ]}

• Una herramienta escrita en Java
• Conectores basados ​​en conos en la biblioteca de algoritmos de geometría computacional (CGAL)

• Gráfico de Yao
• Gráfico Semi-Yao
• llave geométrica