Gráfico de Urquhart

En geometría computacional , el grafo de Urquhart de un conjunto de puntos en el plano, que recibe su nombre de 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).${\displaystyle p}$y${\displaystyle q}$cuando no existe ningún tercer punto${\displaystyle r}$que está más cerca de ambos${\displaystyle p}$y${\displaystyle q}$que entre sí). Dado que las triangulaciones de Delaunay se pueden construir en el tiempo${\displaystyle O(n\log n)}$, el mismo límite de tiempo se cumple también para el grafo de Urquhart. ^{[ 1 ]} Aunque posteriormente se demostró que el grafo de Urquhart no es exactamente igual al grafo de vecindad relativa, ^{[ 2 ]} puede utilizarse como una buena aproximación al mismo. ^{[ 3 ]} El problema de construir grafos de vecindad relativa en${\displaystyle O(n\log n)}$El problema del tiempo, que quedó abierto debido al desajuste entre el grafo de Urquhart y el grafo de vecindad relativa , fue resuelto por Supowit (1983) . ^{[ 4 ]}

Al igual que el grafo de vecindad relativa, el grafo de Urquhart de un conjunto de puntos en posición general contiene el árbol de expansión mínima euclidiana de sus puntos, de lo cual se deduce que es un grafo conexo .