En geometría computacional, el grafo theta, o grafo , es un tipo de extensor geométrico similar a un grafo de Yao. El método básico de construcción consiste en dividir el espacio alrededor de cada vértice en un conjunto de conos, que a su vez separan los vértices restantes del grafo. Al igual que los grafos de Yao, un grafo contiene como máximo una arista por cono; la diferencia radica en cómo se selecciona dicha arista. Mientras que en los grafos de Yao se selecciona el vértice más cercano según el espacio métrico del grafo, en el grafo se 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 dicho rayo. El grafo resultante presenta varias buenas propiedades de extensión..

Los grafos fueron (descritos en primer lugar por ClarksonK. Clarkson. 1987. Approximation algorithms for shortest path motion planning. In Proceedings of the nineteenth annual ACM symposium on Theory of computing (STOC '87), Alfred V. Aho (Ed.). ACM, New York, NY, USA, 56–65. en 1987 e independientemente por KeilKeil, J. (1988). Approximating the complete Euclidean graph. SWAT 88, 208–213. en 1988.

Construcción Los grafos se especifican con algunos parámetros que determinan su construcción. El parámetro más obvio es , 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 , un cono alrededor de puede imaginarse como dos rayos infinitos que emanan de él con un ángulo entre ellos. Con respecto a , se pueden etiquetar estos conos como a en sentido antihorario desde , que convencionalmente se abre de manera que su bisectriz tenga un ángulo de 0° con respecto al plano. Como estos conos dividen el plano, también dividen el conjunto de vértices restante del grafo (suponiendo que se hayan en una posición general) en los conjuntos a , nuevamente con respecto a . Cada vértice del grafo recibe el mismo número de conos en la misma orientación, y se puede considerar el conjunto de vértices que caen en cada uno.

Considerando un solo cono, se necesita especificar otro rayo que emana de , denominado . Para cada vértice en , se considera la proyección ortogonal de cada sobre . Supóngase ahora que es el vértice con la proyección más cercana. Entonces, la arista se agrega al grafo. Esta es la principal diferencia con los grafos de Yao, que siempre se selecciona el vértice con la proyección más cercana. En la imagen de ejemplo, un grafo de Yao incluiría la arista en su lugar.

La construcción de un grafo es posible con un algoritmo de línea de barrido en tiempo .

Propiedades Los grafos presentan varias propiedades útiles como extensor geométrico.

Cuando el parámetro es constante, el grafo es un extensor 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 aristas.

El factor de estiramiento entre cualquier par de puntos en un extensor se define como la razón entre su distancia en el espacio métrico y su distancia dentro del extensor (es decir, desde las aristas siguientes del extensor). El factor de estiramiento de todo el extensor es el factor de estiramiento máximo sobre todos los pares de puntos dentro de él. Debe recordarse que , entonces, cuando , el grafo tiene un factor de estiramiento de como máximo . Si la línea de proyección ortogonal en cada cono se elige como la bisectriz, entonces para , la razón de expansión es como máximo .Ruppert, J., & Seidel, R. (1991). Approximating the d-dimensional complete Euclidean graph. In Proc. 3rd Canad. Conf. Comput. Geom (pp. 207–210).

Para , el grafo forma un grafo del vecino más cercano. Para , es fácil ver que el grafo es conexo, ya que cada vértice se conectará con algo a su izquierda y algo a su derecha, si existen. Para ,, ,. ,. ,Bonichon, N., Gavoille, C., Hanusse, N., & Ilcinkas, D. (2010). Connections between theta-graphs, Delaunay triangulations, and orthogonal surfaces. In Graph Theoretic Concepts in Computer Science (pp. 266–278). Springer Berlin/Heidelberg. y , se sabe que el grafo es conexo. Muchos de estos resultados también proporcionan cotas superiores y/o inferiores para sus razones de extensión.

Cuando es un número par, se puede crear una variante del grafo conocida como el semigrafo , donde los conos se dividen en conjuntos pares e impares de forma alternada, y las aristas solo se consideran en los conos pares (o solo en los impares). Se sabe que los semigrafos poseen propiedades muy interesantes. Por ejemplo, el semigrafo (y, por consiguiente, el grafo , que es la unión de dos grafos complementarios se conoce como un 2-extensor.

Software para dibujar grafos Theta Herramienta escrita en Java Cone-based Spanners en la Biblioteca de Algoritmos de Geometría Computacional (CGAL)

Véase también Grafo de Yao Semigrafo de Yao Extensor geométrico

Referencias

Categoría:Geometría computacional Categoría:Teoría de grafos geométricos