Theta Grafo (Theta Graph, θG)
Este grafo fue desarrollado y propuesto por Clarkson y Keil a finales de los años ochenta. Se trata de una variación del Grafo de Yao; su definición es exactamente igual con el único cambio de que cada vértice v no se une con el más cercano de cada sector, sino con el vértice cuya proyección ortogonal sobre el semieje que separa cada región (se puede elegir el semieje que queda a la izquierda o derecha de los puntos, pero siempre utilizando el mismo criterio en todo el grafo) tiene la distancia menor a v.
Del párrafo anterior deducimos que la idea principal es procesar cada punto p del espacio de puntos de manera independiente. Vamos a realizar una partición de plano en k conos de diámetro angular θ y vértice el punto p, donde k = 2π/θ. Para cada cono no vacío C, se une una arista que enlaza p y el punto de C cuya proyección ortogonal sobre el semieje es más cercana a p. La figura siguiente nos ayuda a comprender de un modo más gráfico lo explicado anteriormente:
Ilustración Aristas del Grafo θ para k=6, y Grafo θ
La definición del theta grafo puede extenderse a dimensión d.
Propiedad 1: Si S es un conjunto de puntos del plano y k ≥ 2 es una constante, entonces el θ-grafo correspondiente contiene a lo sumo kn = (2π / θ)n = O (n) aristas.
Demostraremos ahora que el theta grafo es un t-spanner para el grafo completo definido sobre un conjunto de puntos en el plano S, con t = 1 / (cos θ - sin θ). Para ello necesitamos el siguiente resultado previo.
Lema: Sea θ=2π/k, p, q, r puntos tales que q,r están en el mismo cono con respecto a p y la proyección de r es más próxima a p que la de q. Entonces:
1. |pr| ≤ |pq| / cos θ
2. |rq| ≤ |pq| - (cos θ - sin θ) |pr|
Demostración:
Asumiremos en la demostración que r es distinto de q. Sea q´ la proyección ortogonal de q en lC,p y sea α el ángulo formado por los segmentos pq y pq´. Consideramos que 0 ≤ α ≤ θ. Entonces:
|pq´| = |pq| cos α ≤ |pq|.
Del mismo modo, sea r´ la proyección ortogonal de r en en lC,p y sea β el ángulo formado por los segmentos pr y pr´. Si 0 ≤ β ≤ θ. Entonces:
|pr´| = |pr| cos β ≥ |pr| cos θ
Asumiendo que |pr´| ≤ |pq´|, entonces tenemos que:
|pr´| cos θ ≤ |pr´| ≤ |pq´| ≤ |pq|.
De este modo queda demostrado el primer punto del lema. Para poder demostrar el segundo punto, consideramos l como la línea existente entre p y q, y s será la proyección ortogonal de r en dicha línea. Vamos a considerar que |ps| ≤ |pq|, aunque la demostración para el caso contrario es análoga. Si analizamos p, s y r como los vértices de un triángulo escaleno y aplicamos las leyes matemáticas de la inecuación del triángulo, tenemos.
|rq| ≤ |rs| + |sq|
= |rs| + |pq| - |ps|
≤ |pr| sin θ + |pq| - |pr| cos θ
= |pq| - (cos θ – sin θ) |pr|.
Teorema: Si k ≥ 9, θ=2π/k y S es un conjunto de puntos del plano entonces el θ-grafo correspondiente, θ (S, k), es un t-spanner para S, con t = 1 / (cos θ - sin θ).
Demostración.
Si k ≥ 9, entonces 0 ≤ θ < π / 4. Dados dos puntos p y q de S construiremos un camino P* en θ(S, k) entre p y q cuya longitud verifica la condición para que el grafo sea un t-spanner.
Si P* es el camino {p, p1, p2, ... , q}, el primer punto p1 es el vecino de p en el cono de amplitud q que contiene a q. El segundo punto p2 es el vecino de p1 en el cono (ahora con ápice en p1) que contiene a q. Y así hasta alcanzar q.
Aplicando el lema anterior a pi, pi+1 y q, se tiene que
|pi+1 q| ≤ |piq| - (cos θ – sin θ) |pipi+1| < |piq| (porque k>8)
Con lo que comprobamos que el camino se acerca al destino q. Considerando que pm = q y aplicando la inecuación anterior para cada i que cumpla que 0 ≤ i ≤ m:
|pipi+1| ≤ (|piq| - |pi+1 q|) / (cos θ – sin θ)
Y ahora podemos calcular la longitud del camino sumando estas desigualdades.
Ʃi = 0 |pipi+1| ≤ Ʃi = 0 (|piq| - |pi+1 q|) / (cos θ – sin θ)
= (|p0q| - |pmq|) / (cos θ – sin θ)
= |pq| / (cos θ – sin θ)
Es decir, long(P*) ≤ |pq| / (cos θ – sin θ) y el teorema queda demostrado.
Problemas resultantes
¿Es el theta grafo un buen spanner? Hemos visto que para un número real t > 1, existe un entero k tal que el grafo θ(S, k) es un t-spanner de S. Pero, ¿Es el grado de nuestro grafo pequeño? ¿Tiene nuestro grafo un peso bajo? ¿Qué podemos decir sobre el diámetro spanner?
Partamos de un punto p del espacio S. Consideremos que el resto de puntos n – 1 conforman una red de puntos y aristas. Si k ≥ 9, entonces θ(S, k) contiene una arista entre cada uno de los n – 1 puntos. De este modo, el punto origen p tendrá un grado n – 1 para este grafo. Si n es un número muy alto, el peso del grafo será muy elevado y además incrementará linealmente con n, demostrando que los theta grafos no tienen ni un peso ni un grado bajos.
Consideremos que S es el conjunto de n puntos en el eje de las ordenadas. Sea θ(S, k) la secuencia de puntos, ordenada de izquierda a derecha. El único camino entre el punto de más a la izquierda y el punto de más a la derecha es un camino 1-spanner formado por n – 1 aristas. De este modo, el grafo tendrá un diámetro spanner n – 1, demostrándose que los theta grafo tampoco tienen un diámetro bajo.
Por tanto, hemos conseguido devolver un grafo que presentaba un factor de dilación bajo, pero no hemos conseguido acotar el resto de medidas. En los próximos apartados, vamos a presentar distintas variantes que van a conseguir alcanzar un spanner de diámetro acotado, de grado acotado, y de ambos a la vez.
Antes de comenzar con estas nuevas variantes de theta grafo, conviene dejar aclaradas una serie de nociones previas. El objetivo de las siguientes variantes es conseguir acotar el grado del grafo, el diámetro, o incluso acotar ambos al mismo tiempo de la forma más eficiente posible. En concreto vamos a hablar del spanner de grado acotado, construido en un algoritmo de tiempo O (n log n) para una constante dada t > 1 cuyos vértices tienen un grado acotado por una constante.
Siendo más precisos, consideraremos S como el conjunto de n puntos en el plano, y t´ > 1 será una constante. Sea G un grafo no dirigido t´-spanner para S. Asumimos que en un periodo de tiempo O (n log n) las aristas de G pueden ser dirigidas de tal forma que cada vértice tenga un grado de salida limitado por una constante. Sea t una constante mayor que t´. Vamos a demostrar como transformar G en un t-spanner no dirigido cuyos vértices tendrán un grado acotado por una constante. Esta transformación tardará un tiempo O (n log n).
Cuando hablamos de dirigir aristas, queremos decir que se reemplazará cada arista {p, q} de G bien por la arista dirigida (p, q), bien por la arista dirigida (q, p).
Teorema: El grafo θ-grafo es un t-spanner para S con t = 1 / (cos θ - sin θ). Este grafo contiene O(n / θd-1) aristas y se construye en un tiempo O((n / θd-1) log d-1); usando un espacio O((n / θd-1) + n log d-2 n).