En geometría computacional , el gráfico de Urquhart de un conjunto de puntos en el plano, llamado así por Roderick B. Urquhart, se obtiene quitando el borde más largo de cada triángulo en la triangulación de Delaunay .
El gráfico Urquhart fue descrito por Urquhart (1980) , que sugirió que la eliminación del borde más largo de cada triángulo Delaunay sería una forma rápida de construir el grafo de vecindad relativa (el gráfico de la conexión de pares de puntos p y q cuando no existe ningún tercero punto r que está más cerca de ambos p y q de lo que son el uno al otro). Dado que las triangulaciones de Delaunay se pueden construir en el tiempo O ( n log n ), el mismo límite de tiempo se aplica también al gráfico de Urquhart. [1] Aunque más tarde se demostró que el gráfico de Urquhart no es exactamente el mismo que el gráfico de vecindad relativa,[2] se puede utilizar como una buena aproximación. [3] El problema de construir gráficos de vecindad relativa en el tiempo O ( n log n ), que quedó abierto por el desajuste entre el gráfico de Urquhart y el gráfico de vecindad relativa, fue resuelto por Supowit (1983) . [4]
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, del cual se sigue que es un gráfico conectado .
Referencias
- ^ Urquhart, RB (1980), "Algoritmos para el cálculo del gráfico de vecindad relativa", Electronics Letters , 16 (14): 556–557, doi : 10.1049 / el: 19800386.
- ^ Toussaint, GT , "Comentario: algoritmos para calcular el gráfico de vecindad relativa", Electronics Letters , 16 (22): 860, doi : 10.1049 / el: 19800611. Respuesta de Urquhart, doi : 10.1049 / el: 19800612 págs. 860–861.
- ^ Andrade, Diogo Vieira; de Figueiredo, Luiz Henrique (2001), "Buenas aproximaciones para el gráfico de vecindad relativa", Proc. 13a Conferencia Canadiense de Geometría Computacional (PDF) .
- ^ 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.
