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
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
- ↑ 1,0 et 1,1 Modèle:Article
- ↑ Modèle:Article
- ↑ 3,0 et 3,1 Modèle:Article