Gráfico de Urquhart

Ejemplo de gráfico de Urquhart : se eliminan los bordes más largos (cian delgado) de cada triángulo de Delaunay.

En geometría computacional , el gráfico de Urquhart de un conjunto de puntos en el plano, llamado así en honor a Roderick B. Urquhart, se obtiene eliminando la arista más larga de cada triángulo en la triangulación de Delaunay .

El grafo de Urquhart fue descrito por Urquhart (1980), quien sugirió que eliminar la arista más larga de cada triángulo de Delaunay sería una forma rápida de construir el grafo de vecindad relativa (el grafo que conecta pares de puntos y cuando no existe ningún tercer punto que esté más cerca de ambos y que de ellos entre sí). Dado que las triangulaciones de Delaunay se pueden construir en el tiempo , el mismo límite de tiempo se aplica también al grafo de Urquhart. ^[1] Aunque más tarde se demostró que el grafo de Urquhart no es exactamente el mismo que el grafo de vecindad relativa, ^[2] se puede utilizar como una buena aproximación al mismo. ^[3] El problema de construir grafos de vecindad relativa en el tiempo, que quedó abierto por el desajuste entre el grafo de Urquhart y el grafo de vecindad relativa, fue resuelto por Supowit (1983). ^[4] ${\displaystyle p}$ ${\displaystyle q}$ ${\displaystyle r}$ ${\displaystyle p}$ ${\displaystyle q}$ ${\displaystyle O(n\log n)}$ ${\displaystyle O(n\log n)}$

Al igual que el gráfico de vecindad relativa, el gráfico de Urquhart de un conjunto de puntos en posición general contiene el árbol de expansión mínimo euclidiano de sus puntos, de lo que se deduce que es un gráfico conexo .

Referencias

1. Urquhart, RB (1980), "Algoritmos para el cálculo de gráficos de vecindad relativa", Electronics Letters , 16 (14): 556–557, Bibcode :1980ElL....16..556U, doi :10.1049/el:19800386.
2. Toussaint, GT (1980), "Comentario: Algoritmos para calcular gráficos de vecindad relativa", Electronics Letters , 16 (22): 860, Bibcode :1980ElL....16..860T, doi :10.1049/el:19800611Respuesta de Urquhart, doi :10.1049/el:19800612 pp. 860–861.
3. Andrade, Diogo Vieira; de Figueiredo, Luiz Henrique (2001), "Buenas aproximaciones para el gráfico de vecindad relativa", Proc. 13.a Conferencia Canadiense sobre Geometría Computacional (PDF).
4. Supowit, KJ (1983), "El gráfico de vecindad relativa, con una aplicación a árboles de expansión mínima", J. ACM , 30 (3): 428–448, doi : 10.1145/2402.322386.