Wykres Urquharta

Przykład wykresu Urquharta : najdłuższe krawędzie (cienki cyjan) są usuwane z każdego trójkąta Delaunay.

W geometrii obliczeniowej wykres Urquharta zbioru punktów na płaszczyźnie, nazwany na cześć Rodericka B. Urquharta, jest uzyskiwany przez usunięcie najdłuższej krawędzi z każdego trójkąta w triangulacji Delaunaya .

Wykres Urquharta został opisany przez Urquharta (1980) , który zasugerował, $że$ usunięcie najdłuższej krawędzi z każdego trójkąta Delaunaya byłoby szybkim sposobem skonstruowania wykresu względnego sąsiedztwa (wykres łączący pary punktów $\ displaystyle p}$ q $displaystyle q}$ , gdy nie istnieje żaden trzeci punkt $displaystyle$ który byłby bliższy zarówno $p},$ jak i ${\ displaystyle q}$ niż są względem siebie). $ta sama granica czasowa$ można konstruować w czasie dla wykresu Chociaż później wykazano, że wykres Urquharta nie jest dokładnie taki sam jak wykres względnego sąsiedztwa, można go użyć jako dobrego przybliżenia. Problem konstruowania grafów względnego sąsiedztwa w ${\ Displaystyle O (n \ log n)}$ czas, pozostawiony otwarty przez niedopasowanie między wykresem Urquharta a grafem względnego sąsiedztwa, został rozwiązany przez Supowita (1983) .

Podobnie jak wykres względnego sąsiedztwa, wykres Urquharta zbioru punktów w pozycji ogólnej zawiera euklidesowe drzewo rozpinające jego punkty, z którego wynika, że ​​jest to graf spójny .