Naar inhoud springen

Urquhartgraaf

Uit Wikipedia, de vrije encyclopedie
In dit voorbeeld vormen de dikke lijnen de Urquhartgraaf, bekomen door de langste zijde te verwijderen van elke driehoek in de Delaunay-triangulatie (cyaankleurige lijnen)

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)