Girig geometrisk skiftnyckel

Girig geometrisk nyckel med 100 slumpmässiga punkter med sträckfaktor t = 2

Girig geometrisk skiftnyckel med samma punkter med sträckfaktor t = 1,1

Inom beräkningsgeometri är en girig geometrisk skiftnyckel en oriktad graf vars avstånd approximerar de euklidiska avstånden bland en ändlig uppsättning punkter i ett euklidiskt utrymme . Topparna på grafen representerar dessa punkter. Nyckelns kanter väljs av en girig algoritm som inkluderar en kant när dess två ändpunkter inte är sammankopplade med en kort bana med kortare kanter. Den giriga nyckeln beskrevs först i Gautam Das doktorsavhandling och konferensbidrag och efterföljande tidskriftsuppsats av Ingo Althöfer et al. Dessa källor krediterade också Marshall Bern (opublicerad) med den oberoende upptäckten av samma konstruktion.

Giriga geometriska skiftnyckel har avgränsad grad , ett linjärt totalt antal kanter och totalvikt nära det av den euklidiska minsta spännande trädet . Även om kända konstruktionsmetoder för dem är långsamma, är snabba approximationsalgoritmer med liknande egenskaper kända.

Konstruktion

Den giriga geometriska nyckeln bestäms från en indata som består av en uppsättning punkter och en parameter $t\geq 1$ . Målet är att konstruera en graf vars kortaste vägavstånd är högst $t$ gånger de geometriska avstånden mellan punkterpar. Den kan vara konstruerad av en girig algoritm som lägger till kanter en i taget till grafen, med början från en kantlös graf med punkterna som sina hörn. Alla poängpar betraktas i sorterad (stigande) ordning efter deras avstånd, med början med det närmaste paret . För varje par $(u,v)$ av punkter, testar algoritmen om grafen som konstruerats hittills redan innehåller en väg från $u$ till $v$ med längd vid mest $t\cdot d(u,v)$ . Om inte, läggs kanten $uv$ med längden $d(u,v)$ till grafen. Genom konstruktion är den resulterande grafen en geometrisk skiftnyckel med sträckfaktor som högst $t$ .

En naiv implementering av denna metod skulle ta tid $O(n^{3}\log n)$ på ingångar med $n$ punkter. Detta beror på att övervägandena för vart och ett av punktparen ${\displaystyle O(n^{2})} involverar en instans av$ Dijkstras algoritm för att hitta en kortaste väg i en graf med ${\ displaystyle O(n)}$ kanter. Den använder $O(n^{2})$ utrymme för att lagra den sorterade listan med punkter. Mer noggranna algoritmer kan konstruera samma graf i tid $O(n^{2}\log n)$ , eller i rymden $O(n)$ . En konstruktion för en variant av den giriga skiftnyckeln som använder grafklustring för att snabbt approximera grafens avstånd löper i tiden $O(n\log n)$ i euklidiska rum av valfri avgränsad dimension, och kan producera skiftnycklar med (ungefär) samma egenskaper som de giriga nycklarna. Samma metod kan utökas till utrymmen med avgränsad dubbleringsdimension .

Egenskaper

Samma giriga konstruktion ger skiftnycklar i godtyckliga metriska utrymmen , men i euklidiska utrymmen har den goda egenskaper av vilka några inte håller mer generellt.

Den giriga geometriska skruvnyckeln i valfritt metriskt utrymme innehåller alltid det minsta spännträdet för dess indata, eftersom den giriga konstruktionsalgoritmen följer samma insättningsordning av kanter som Kruskals algoritm för minsta spännträd. Om den giriga nyckelalgoritmen och Kruskals algoritm körs parallellt, med tanke på samma par av hörn i samma ordning, kommer varje kant som läggs till av Kruskals algoritm också att läggas till av den giriga nyckelalgoritmen, eftersom kantens ändpunkter inte redan kommer att vara förbundna med en väg. I begränsningsfallet när $t$ är tillräckligt stor (t.ex. $t>n$ , där $n$ är antalet hörn i grafen) ger de två algoritmerna samma utdata .

I euklidiska utrymmen med avgränsad dimension, för varje konstant $t$ , har de giriga geometriska $t$ -nyckeln på uppsättningar av $n$ punkter avgränsad grad , vilket antyder att de också har $O(n)$ kanter. Den här egenskapen sträcker sig inte ens till väluppfostrade metriska utrymmen: det finns utrymmen med begränsad dubbleringsdimension där den giriga skiftnyckeln har obegränsad vertexgrad. Men i sådana utrymmen är antalet kanter fortfarande $O(n)$ .

Giriga geometriska skiftnycklar i euklidiska utrymmen med avgränsade dimensioner har också totalvikten som mest konstant gånger den totala vikten av det euklidiska minimumspännande trädet . Denna egenskap förblir sann i utrymmen med avgränsad dubbleringsdimension.