Wykres Yao
W geometrii obliczeniowej wykres Yao , nazwany na cześć Andrew Yao , jest rodzajem klucza geometrycznego , ważonego niekierowanego wykresu łączącego zbiór punktów geometrycznych z właściwością, że dla każdej pary punktów na wykresie ich najkrótsza ścieżka ma długość czyli mieści się w stałym współczynniku ich odległości euklidesowej .
Podstawową ideą leżącą u podstaw dwuwymiarowego wykresu Yao jest otoczenie każdego z podanych punktów równo rozmieszczonymi promieniami , dzieląc płaszczyznę na sektory o równych kątach i połączenie każdego punktu z najbliższym sąsiadem w każdym z tych sektorów. Z wykresem Yao związany jest parametr całkowity k ≥ 6 , który jest liczbą promieni i sektorów opisanych powyżej; większe wartości k dają bliższe przybliżenia odległości euklidesowej. Współczynnik rozciągania wynosi co najwyżej jest kątem sektorów. Ten sam pomysł można rozszerzyć na zbiory punktów w więcej niż dwóch wymiarach, ale liczba wymaganych sektorów rośnie wykładniczo wraz z wymiarem.
Andrew Yao użył tych wykresów do skonstruowania wielowymiarowych drzew euklidesowych o minimalnej rozpiętości .