Chamtivý geometrický klíč - Greedy geometric spanner

Chamtivý geometrický klíč 100 náhodných bodů s faktorem roztažení t = 2

Chamtivý geometrický klíč stejných bodů s faktorem roztažení t = 1.1

v výpočetní geometrie, a chamtivý geometrický klíč je neorientovaný graf jehož vrcholy představují body v a Euklidovský prostor, a jejichž hrany jsou vybrány a chamtivý algoritmus udělat nejkratší cesta vzdálenosti v grafu (s hranami váženými podle délky) se blíží Euklidovské vzdálenosti mezi dvojicemi bodů. Konstrukci chamtivých klíčů poprvé publikoval Ingo Althöfer et al. v roce 1993; jejich práce také připisovala Marshallovi Bernovi (nepublikováno) nezávislý objev stejné konstrukce.^[1]

Chamtivé geometrické klíče ohraničené stupeň, lineární celkový počet hran a celková hmotnost blízká hmotnosti Euklidovský minimální kostra. Ačkoli známé konstrukční metody pro ně jsou pomalé, rychlé aproximační algoritmy s podobnými vlastnostmi jsou známy.^[2]

Konstrukce

Chamtivý geometrický klíč je určen ze vstupu sestávajícího ze sady bodů a parametru ${ displaystyle t geq 1}$. Cílem je sestrojit graf, jehož nejkratší dráhy jsou maximálně ${ displaystyle t}$ krát geometrické vzdálenosti mezi dvojicemi bodů. To může být postaveno a chamtivý algoritmus který přidává do grafu hrany po jedné, počínaje znakem bez okrajů graf s body jako jeho vrcholy. Všechny páry bodů jsou považovány v seřazeném (vzestupném) pořadí podle jejich vzdáleností, počínaje nejbližší pár. Pro každý pár ${ displaystyle (u, v)}$ bodů algoritmus testuje, zda dosud vytvořený graf již obsahuje cestu z ${ displaystyle u}$ na ${ displaystyle v}$ s délkou maximálně ${ displaystyle t cdot d (u, v)}$. Pokud ne, okraj ${ displaystyle uv}$ s délkou ${ displaystyle d (u, v)}$ Konstrukcí je výsledný graf a geometrický klíč s napínací faktor nejvíce ${ displaystyle t}$.^[1]

Naivní implementace této metody by vyžadovala čas ${ displaystyle O (n ^ {3} log n)}$ na vstupech s ${ displaystyle n}$ bodů. Je to proto, že úvahy pro každou z nich ${ displaystyle O (n ^ {2})}$ dvojice bodů zahrnuje instanci Dijkstrův algoritmus najít nejkratší cestu v grafu pomocí ${ displaystyle O (n)}$ hrany. Využívá to ${ displaystyle O (n ^ {2})}$ prostor pro uložení seřazeného seznamu dvojic bodů. Pečlivější algoritmy mohou vytvořit stejný graf v čase ${ displaystyle O (n ^ {2} log n)}$,^[3] nebo ve vesmíru ${ displaystyle O (n)}$.^[4]Konstrukce pro variantu chamtivého klíče, která využívá shlukování grafů k rychlé aproximaci vzdáleností grafů, probíhá v čase ${ displaystyle O (n log n)}$ v euklidovských prostorech jakékoli ohraničené dimenze a může vytvářet klíče s (přibližně) stejnými vlastnostmi jako chamtivé klíče.^[5][6] Stejnou metodu lze rozšířit na mezery s ohraničením zdvojnásobení dimenze.^[2]

Vlastnosti

Stejná chamtivá konstrukce vytváří svévolně klíče metrické prostory, ale v euklidovských prostorech má dobré vlastnosti, z nichž některé obecněji nedrží.^[2]

Chamtivý geometrický klíč v jakémkoli metrickém prostoru vždy obsahuje minimální kostra jeho vstupu, protože chamtivý konstrukční algoritmus sleduje stejné pořadí vkládání hran jako Kruskalův algoritmus pro minimální kostry. Pokud jsou chamtivý klíčový algoritmus a Kruskalův algoritmus spuštěny paralelně, s ohledem na stejné páry vrcholů ve stejném pořadí, každá hrana přidaná Kruskalovým algoritmem bude také přidána chamtivým klíčovým algoritmem, protože koncové body hrany již nebudou spojené cestou. V omezujícím případě, kdy ${ displaystyle t}$ je dostatečně velký (např. ${ displaystyle t> n}$, kde ${ displaystyle n}$ je počet vrcholů v grafu), oba algoritmy produkují stejný výstup.^[1]

V euklidovských prostorech ohraničené dimenze pro jakoukoli konstantu ${ displaystyle t}$chamtivý geometrický ${ displaystyle t}$-rozpěrky na sadách ${ displaystyle n}$ body jsou ohraničené stupeň, což znamená, že také mají ${ displaystyle O (n)}$ hrany.^[7][8][5] Tato vlastnost se nevztahuje ani na dobře chované metrické prostory: existují mezery s ohraničením zdvojnásobení dimenze kde chamtivý klíč má neomezený stupeň vrcholu.^[2][9][10] V takových prostorech je však počet hran stále ${ displaystyle O (n)}$.^[2]

Chamtivé geometrické klíče v euklidovských prostorech s omezenou dimenzí mají také celkovou hmotnost nanejvýš konstantní násobek celkové hmotnosti Euklidovský minimální kostra.^[7][8][5]Tato vlastnost zůstává pravdivá v prostorech ohraničené zdvojené dimenze.^[2]

Reference