Urquhartgraaf
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.[1] 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[2] 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.[3]
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)
- ↑ R.B. Urquhart: "Algorithms for computation of relative neighbourhood graph." 'Electronics Letters, Vol. 16 nr. 14 (3 juli 1980), pp. 556-557
- ↑ G.T. Toussaint, "Comment: Algorithms for computing relative neighbourhood graph", met antwoord van R.B. Urquhart. Electronics Letters, Vol. 16 nr. 22 (23 october 1980), pp. 860-861
- ↑ Diogo Vieira Andrade en Luiz Henrique de Figueiredo. "Good Approximations for the Relative Neighbourhood Graph". Proc. 13th Canadian Conference on Computational Geometry (2001)