Klucz geometryczny

Klucz geometryczny lub $t$ -kluczowy lub $t$ -kluczowy został początkowo wprowadzony jako wykres ważony na zbiorze punktów jako jego wierzchołki, dla których istnieje ścieżka t $między$ dowolną parą wierzchołków dla ustalonego parametru $t$ . Ścieżka $t$ jest zdefiniowana jako ścieżka przez wykres o wadze co najwyżej $t$ razy odległość przestrzenna między jego punktami końcowymi. Parametr $t$ nazywany jest współczynnikiem rozciągania lub współczynnikiem rozszerzalności klucza.

W geometrii obliczeniowej koncepcja ta została po raz pierwszy omówiona przez LP Chew w 1986 r., Chociaż termin „klucz” nie był używany w oryginalnym artykule.

Pojęcie kluczy grafowych jest znane w teorii grafów : $t$ -klucze obejmują podgrafy grafów o podobnych właściwościach dylatacji, gdzie odległości między wierzchołkami grafu są zdefiniowane w terminach grafowo-teoretycznych . Dlatego klucze geometryczne to klucze grafowe kompletnych grafów osadzonych w płaszczyźnie o wagach krawędzi równych odległościom między osadzonymi wierzchołkami w odpowiedniej metryce.

Klucze mogą być używane w geometrii obliczeniowej do rozwiązywania niektórych problemów związanych z bliskością . Znaleźli również zastosowania w innych obszarach, takich jak planowanie ruchu , w sieciach telekomunikacyjnych : niezawodność sieci, optymalizacja roamingu w sieciach komórkowych itp.

Różne klucze i miary jakości

Istnieją różne miary, które można wykorzystać do analizy jakości klucza. Najczęstszymi miarami są liczba krawędzi, całkowita waga i maksymalny stopień wierzchołka . Asymptotycznie optymalne wartości dla tych miar $}$ krawędzie waga i $Displaystyle$ $)$ stopień (tutaj MST oznacza wagę minimalnego drzewa rozpinającego ).

że znalezienie klucza na płaszczyźnie euklidesowej z minimalnym rozszerzeniem na n punktach z maksymalnie m krawędziami jest NP-trudne .

Istnieje wiele algorytmów klucza, które wyróżniają się różnymi miarami jakości. Szybkie $z$ obejmują klucz WSPD i wykres Theta klucze z liniową liczbą krawędzi . Jeśli wymagana jest lepsza waga i stopień wierzchołka, klucz zachłanny można obliczyć w czasie zbliżonym do kwadratu.

Wykres Theta

Wykres Theta lub $-graf należy$ . rodziny kluczy stożkowych Podstawowa metoda konstrukcji polega na podziale przestrzeni wokół każdego wierzchołka na zbiór stożków, które same dzielą pozostałe wierzchołki grafu. Podobnie jak $wykresy$ Yao , zawiera co najwyżej jedną krawędź na stożek; gdzie się różnią, to sposób wybrania tej krawędzi. Podczas gdy Yao Graphs wybierze najbliższy wierzchołek zgodnie z przestrzenią metryczną wykresu, wykres definiuje stały promień zawarty w każdym stożku (konwencjonalnie dwusieczną stożka) i wybiera najbliższego sąsiada pod względem ${\ displaystyle \ Theta}$ do rzutów prostopadłych do tego promienia.

Chciwy klucz

Chciwy klucz lub graf zachłanny definiuje się jako wykres będący wynikiem wielokrotnego dodawania krawędzi między najbliższą parą punktów bez ścieżki t . Algorytmy, które obliczają ten wykres, nazywane są algorytmami zachłannego klucza. Z konstrukcji trywialnie wynika, że graf zachłanny jest t -kluczem.

Chciwy klucz został po raz pierwszy opisany w rozprawie doktorskiej Gautama Dasa i artykule konferencyjnym, a następnie w artykule 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.

Chciwy klucz osiąga asymptotycznie optymalną liczbę krawędzi, całkowitą wagę i maksymalny stopień wierzchołka, a także najlepiej sprawdza się w praktyce w przypadku tych miar. Można go skonstruować w ${2})$ $Displaystyle O$ przestrzeni ^

Triangulacja Delaunaya

Głównym wynikiem Chew było to, że dla zbioru punktów na płaszczyźnie istnieje triangulacja tego zbioru punktów w taki sposób, że dla dowolnych dwóch punktów istnieje ścieżka wzdłuż krawędzi triangulacji o długości co najwyżej ${\ displaystyle {\ sqrt {1} }0}$ odległość euklidesowa między dwoma punktami. Wynik został zastosowany w planowaniu ruchu do znajdowania rozsądnych przybliżeń najkrótszych ścieżek wśród przeszkód.

Najlepsza górna granica znana z triangulacji Euklidesa $,$ polega na tym że jest ona kluczem dla swoich wierzchołków. Dolna granica została zwiększona z nieco powyżej, do 1,5846 ${\ displaystyle {{\ pi}/2}}$

Rozkład dobrze rozdzielonych par

Klucz można zbudować z rozkładu dobrze rozdzielonych par w następujący sposób. $Skonstruuj$ wykres z zestawem punktów $jako$ wierzchołków i dla każdej pary ${\ Displaystyle a \ w A}$ krawędź z do dowolnego punktu ${\ Displaystyle b \ w B}$ . Zauważ, że wynikowy wykres ma liniową liczbę krawędzi, ponieważ WSPD ma liniową liczbę par.

Możliwe jest uzyskanie dowolnej wartości przez $rozkładu$ dobrze rozdzielonych par.