title: Urquhartgraaf
text: De Urquhartgraaf (UG) van een verzameling S van punten in het vlak is een deelgraaf van de Delaunay-triangulatie (DT) van S. De Urquhartgraaf bekomt men door van elke driehoek in de Delaunay-triangulatie de langste zijde te verwijderen.
  
  Roderick B. Urquhart stelde in een publicatie uit 1980 voor dat deze constructie een snel algoritme zou leveren om de relative neighborhood graph (RNG) van een verzameling punten te bepalen.<ref>[http://digital-library.theiet.org/content/journals/10.1049/el_19800386 R.B. Urquhart: "Algorithms for computation of relative neighbourhood graph." 'Electronics Letters, Vol. 16 nr. 14 (3 juli 1980), pp. 556-557]</ref> In de RNG zijn twee punten p en q met elkaar verbonden als er geen enkel ander punt is dat dichter bij p en q ligt dan p en q zelf. Maar Godfried Toussaint, de bedenker van de RNG,  toonde met een tegenvoorbeeld aan dat in het algemeen de RNG slechts een deelgraaf van de Urquhartgraaf is. De Urquhartgraaf is dus niet altijd gelijk aan de RNG maar is er wel een goede benadering van.
  
  De Gabrielgraaf (GG) is een graaf waarin twee punten p en q verbonden zijn als de cirkel met diameter pq geen andere punten van de verzameling S omvat. Deze graaf ligt tussen de UG en de Delaunay-triangulatie in. In het algemeen geldt:
  
  RNG(S) ⊆ UG(S) ⊆ GG(S) ⊆ DT(S'')
  
  Grafentheorie
  Meetkunde