Wykres semi-Yao
Graf k -semi-Yao ( k -SYG ) zbioru n obiektów P jest geometrycznym grafem bliskości, który został po raz pierwszy opisany w celu przedstawienia kinetycznej struktury danych do utrzymywania wszystkich najbliższych sąsiadów poruszających się obiektów. Został nazwany ze względu na związek z wykresem Yao , który został nazwany na cześć Andrew Yao .
Budowa
K - SYG jest skonstruowany w następujący sposób. Przestrzeń wokół każdego punktu p w P jest podzielona na zestaw wielościennych stożków o kącie otwarcia , co oznacza że kąt każdej pary promieni wewnątrz wielościennego stożka wychodzącego z wierzchołka wynosi co najwyżej , a następnie p łączy się z k punktami P w każdym ze stożków wielościennych, których rzuty na oś stożka są minimalne.
Nieruchomości
- Wykres k -SYG, gdzie k = 1, jest znany jako wykres teta i jest sumą dwóch triangulacji Delaunaya .
- Dla małej i odpowiedniej osi k -SYG daje superwykres wykresu k - najbliższego sąsiada ( k -NNG . Na przykład w 2D, jeśli podzielimy płaszczyznę wokół każdego punktu na sześć klinów o równych kątach i wybierzemy osie stożków w kierunkach dwusiecznych stożka, otrzymamy k -SYG jako supergraf dla k -NNG.