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 el lado más largo de cada triángulo de una triangulación de Delaunay.
Fue descrito por , 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 y puntos cuando no existe un tercer punto que esté más cerca de y de que ellos entre sí). Dado que las triangulaciones de Delaunay se pueden construir en tiempo , el mismo límite de tiempo se aplica al grafo de Urquhart.. Aunque posteriormente se demostró que el grafo de Urquhart no es exactamente igual al grafo de vecindad relativa,. Reply by Urquhart, pp. 860–861. puede utilizarse como una buena aproximación.. El problema de construir grafos de vecindad relativa en tiempo , que quedó abierto debido a la discrepancia entre el grafo de Urquhart y el grafo de vecindad relativa, fue resuelto por ..
Al igual que el grafo de vecindad relativa, el grafo de Urquhart de un conjunto de puntos en una posición general contiene el árbol de extensión mínima euclídea de sus puntos, de lo cual se deduce que es un grafo conexo.
Referencias
Categoría:Geometría computacional Categoría:Grafos geométricos