Graphe d'Urquhart
En géométrie algorithmique, le graphe d'Urquhart est un graphe non orienté qui connecte un ensemble de points dans le plan euclidien. Il est obtenu en supprimant la plus longue arête de chaque triangle de la triangulation de Delaunay. Il est décrit en 1980 par R. B. Urquhart[1] comme un moyen de calculer rapidement le graphe de voisinage relatif, ce qui s'avère finalement faux[2]. Il peut néanmoins servir de bonne approximation de celui-ci[3].
La triangulation de Delaunay pouvant être calculée en temps , il en est de même pour le graphe d'Urquhart[1].
Relations avec d'autres graphes[modifier | modifier le code]
Le graphe d'Urquhart est un sous-graphe de la triangulation de Delaunay ainsi que du graphe de Gabriel[3]. Inversement, il a comme sous-graphe le graphe de voisinage relatif, et, si les points sont en position générale, l'arbre couvrant de poids minimal euclidien.
Notes et références[modifier | modifier le code]
- (en) R. B. Urquhart, « Algorithms for computation of relative neighbourhood graph », Electronics Letters, vol. 16, no 14, , p. 556–557 (ISSN 1350-911X, DOI 10.1049/el:19800386, lire en ligne, consulté le )
- (en) G. T. Toussaint, « Comment: Algorithms for computing relative neighbourhood graph », Electronics Letters, vol. 16, no 22, , p. 860–860 (ISSN 1350-911X, DOI 10.1049/el:19800611, lire en ligne, consulté le )
- (en) Diogo Vieira Andrade et Luiz Henrique de Figueiredo, « Good Approximations for the Relative Neighbourhood Graph », 13th Canadian Conference on Computational Geometry, (lire en ligne)
