Chciwy klucz geometryczny
W geometrii obliczeniowej zachłanny klucz geometryczny to graf nieskierowany , którego odległości są zbliżone do odległości euklidesowych między skończonym zbiorem punktów w przestrzeni euklidesowej . Wierzchołki wykresu reprezentują te punkty. Krawędzie klucza są wybierane za pomocą zachłannego algorytmu , który zawiera krawędź, gdy jego dwa punkty końcowe nie są połączone krótką ścieżką o krótszych krawędziach. Chciwy klucz został po raz pierwszy opisany w rozprawie doktorskiej Gautama Dasa oraz artykuł konferencyjny i późniejszy artykuł w czasopiśmie autorstwa Ingo Althöfera i in. Źródła te przypisują również Marshallowi Bernowi (niepublikowane) niezależne odkrycie tej samej konstrukcji.
Chciwe klucze geometryczne mają ograniczony stopień , liniową całkowitą liczbę krawędzi i całkowitą wagę zbliżoną do euklidesowego minimalnego drzewa rozpinającego . Chociaż znane metody ich konstrukcji są powolne, znane są szybkie algorytmy aproksymacyjne o podobnych właściwościach.
Budowa
Chciwy klucz geometryczny jest określany na podstawie danych wejściowych składających się ze zbioru punktów i parametru . Celem jest skonstruowanie wykresu, którego najkrótsze odległości między ścieżkami są co najwyżej odległości geometryczne między parami punktów. Może być skonstruowany przez zachłanny algorytm , który dodaje krawędzie do grafu pojedynczo, zaczynając od grafu bez krawędzi z punktami jako wierzchołkami. Rozpatrywane są wszystkie pary punktów, posortowane (rosnąco) według ich odległości, zaczynając od najbliższa para . Dla każdej pary algorytm sprawdza, czy dotychczas skonstruowany wykres zawiera już ścieżkę u długości większość . Jeśli krawędź o jest dodawany do wykresu. Z konstrukcji wynikowy wykres jest kluczem geometrycznym ze współczynnikiem rozciągania co najwyżej .
wymagałaby _ _ Dzieje się tak ponieważ rozważania dotyczące każdej z obejmują wystąpienie na wykresie z krawędzie. Wykorzystuje par punktów Ostrożniejsze algorytmy mogą skonstruować ten sam wykres w czasie ( ) Konstrukcja dla wariantu zachłannego klucza, który wykorzystuje grupowanie grafów do szybkiego przybliżenia odległości grafów, przebiega w czasie w przestrzeniach euklidesowych o dowolnym ograniczonym wymiarze i może wytwarzać klucze o (w przybliżeniu) takich samych właściwościach, jak chciwe klucze. Tę samą metodę można rozszerzyć na przestrzenie o ograniczonym wymiarze podwajającym .
Nieruchomości
Ta sama zachłanna konstrukcja wytwarza klucze w dowolnych przestrzeniach metrycznych , ale w przestrzeniach euklidesowych ma dobre właściwości, z których niektóre nie są bardziej ogólne.
Zachłanny klucz geometryczny w dowolnej przestrzeni metrycznej zawsze zawiera minimalne drzewo rozpinające swojego wejścia, ponieważ zachłanny algorytm konstrukcyjny jest zgodny z tą samą kolejnością wstawiania krawędzi, co algorytm Kruskala dla minimalnych drzew rozpinających. Jeśli algorytm zachłannego klucza i algorytm Kruskala są uruchomione równolegle, biorąc pod uwagę te same pary wierzchołków w tej samej kolejności, każda krawędź dodana przez algorytm Kruskala zostanie również dodana przez algorytm zachłannego klucza, ponieważ punkty końcowe krawędzi nie będą już połączone ścieżką. W granicznym przypadku, gdy jest wystarczająco duży (np. jest na wykresie), oba algorytmy dają ten sam
przestrzeniach euklidesowych o ograniczonym wymiarze, dla dowolnej stałej zachłanne geometryczne na zestawach punktów mają ograniczony , co oznacza mają również . Ta właściwość nie rozciąga się nawet na dobrze wychowane przestrzenie metryczne: istnieją przestrzenie z ograniczonym wymiarem podwajania gdzie zachłanny klucz ma nieograniczony stopień wierzchołka. Jednak w takich przestrzeniach liczba krawędzi nadal wynosi .
Chciwe klucze geometryczne w przestrzeniach euklidesowych o ograniczonych wymiarach również mają całkowitą wagę co najwyżej stałą razy całkowitą wagę euklidesowego minimalnego drzewa rozpinającego . Własność ta pozostaje prawdziwa w przestrzeniach o ograniczonym wymiarze podwojonym.