Geometrisk ram

Geometrisk skiftnyckel eller t -spann graph , eller t - spanning graph introducerades ursprungligen som en viktad graf på en uppsättning punkter som hörn, för vilka det finns en t - bana mellan valfritt par av hörn för en fast parameter t . En t -bana definieras som en väg i en graf med en vikt som inte överstiger t gånger det rumsliga avståndet mellan ändpunkterna. Parametern t kallas skelettets sträckfaktor [1] .

Inom beräkningsgeometri diskuterades konceptet först av L.P. Chu 1986 [2] , även om termen "nyckel" (skelett) inte nämndes i artikeln.

Konceptet att spänna träd är känt inom grafteorin - t - skelett, dessa är spännande subgrafer av grafer med liknande sträckningsegenskaper, där avståndet mellan grafens hörn definieras i termer av grafteori. Därför är geometriska träd som sträcker sig över träd av kompletta grafer inbäddade i planet , där vikterna på kanterna är lika med avstånden mellan hörnen i motsvarande mått.

Skelett kan användas i beräkningsgeometri för att lösa vissa närhetsproblem . De hittar även applikationer inom andra områden som trafikplanering , kommunikationsnätverk - nättillförlitlighet, roamingoptimering i mobilnät etc.

Olika ryggraden och kvalitetsmått

Det finns olika mått som används för att analysera kvaliteten på kärnorna. De vanligaste måtten är antalet kanter, den totala vikten och den maximala graden av hörn. De asymptotiskt optimala värdena för dessa mått är kanterna, den totala vikten och den maximala graden (där MST betyder vikten av det minsta spännträdet ). $På)$ $O(MST)$ $O(1)$

Det är känt att hitta ett spännande träd i det euklidiska planet med minimal sträckning vid n punkter med högst m kanter är ett NP-hårt problem [3] .

Det finns många algoritmer som fungerar bra under olika kvalitetsmått. Snabba algoritmer inkluderar välseparerade parupplösning ( ) och tetagrafer , som bygger spännvidder med ett linjärt antal kanter i tiden . Om bättre vertexvikter och grader krävs beräknas den giriga spännvidden i nästan kvadratisk tid. $O(n\log n)$

Theta graph

Theta-graf eller -graf tillhör familjen spännvidder baserade på en kon. Den huvudsakliga konstruktionsmetoden är att dela upp utrymmet runt varje vertex i många koner (en platt kon är två strålar, det vill säga en vinkel) som separerar de återstående hörn av grafen. Precis som Yao-graferna innehåller -grafen högst en kant för en kon. Tillvägagångssättet skiljer sig åt i hur kanter väljs. Medan Yao-grafer väljer närmaste vertex enligt det metriska avståndet i grafen, bestämmer -grafen en fast stråle som finns i varje kon (vanligtvis konens bisektrik) och väljer närmaste grannar (dvs de som har det minsta avståndet till strålen) . $\Theta$ $\Theta$ $\Theta$

Girigt skelett

Ett girigt spanande träd eller en girig graf definieras som en graf som erhålls genom att upprepade gånger lägga till en kant mellan punkter som inte har en t -bana. Algoritmer för att beräkna denna graf kallas giriga algoritmer. Det följer trivialt av konstruktionen att giriga grafer är t -skelett.

Den giriga kärnan upptäcktes självständigt 1989 av Althöfer [4] och Bern (opublicerad).

Det giriga skelettet uppnår det asymptotiskt optimala antalet kanter, totalvikt och maximal vertexgrad och ger de bästa mätvärdena i praktiken. Det kan byggas i tid med hjälp av rymden [5] . $O(n^{2}\log n)$ $O(n^{2})$

Delaunay triangulering

Chus huvudresultat var att det för en uppsättning punkter i ett plan existerar en triangulering av dessa uppsättningar av punkter så att det för två godtyckliga punkter finns en bana längs kanterna på trianguleringen med en längd som inte överstiger det euklidiska avståndet mellan de två punkterna . Resultatet användes i trafikplaneringen för att hitta en acceptabel approximation av den kortaste vägen bland hindren. $\scriptstyle {\sqrt {1}}0$

Den mest kända övre gränsen för en Delaunay-triangulering är -skelettet för dess hörn [6] . Den nedre gränsen har höjts från till 1,5846 [7] . $\scriptstyle {(4{\sqrt {3}}/9)\pi }\approx 2{,}418$ $\scriptstyle {{\pi }/2}$

En väl separerad uppdelning av par

Skelettet kan konstrueras från en helt separerad nedbrytning av par enligt följande. Vi bygger en graf med en uppsättning punkter som hörn och för varje par i WSPD lägger vi till en kant från en godtycklig punkt till en godtycklig punkt . Observera att den resulterande grafen har ett linjärt antal kanter, eftersom WSPD har ett linjärt antal par [8] . $S$ $\{A,B\}$ $a\i A$ $b\i B$

Bevis på algoritmens riktighet [9]
Vi behöver dessa två WSPD-egenskaper Lemma 1 : Låta vara en helt separerad sönderdelning av par med avseende på . Låt och . Sedan . $\{A,B\}$ $s$ $p,p'\in A$ $q\in B$ $\|pp'\|\leqslant (2/s)\|pq\|$ Lemma 2 : Låta vara en helt separerad sönderdelning av par med avseende på . Låt och . Sedan, . $\{A,B\}$ $s$ $p,p'\in A$ $q,q'\in B$ $\|p'q'\|\leqslant (1+4/s)\|pq\|$ Låta vara en väl separerad nedbrytning av par med avseende på i WSPD. Låt vara en kant som förbinder med . Låt det finnas en punkt och en punkt . Enligt WSPD-definitionen räcker det att kontrollera att det finns en -backbone path, eller -path för kort, mellan och , som vi betecknar med . Låt oss beteckna väglängden med . $\{A,B\}$ $s$ $[a,b]$ $A$ $B$ $p\in A$ $q\in B$ $t$ $t$ $sid$ $q$ $P_{pq}$ $P_{pq}$ $\|P_{pq}\|$ Antag att det finns en -bana mellan valfritt par av punkter med ett avstånd mindre än eller lika med och . Från triangelns olikhet, antaganden och det faktum att, och enligt Lemma 1, har vi: $t$ $\|pq\|$ $s>2$ $\|pa\|\leqslant (2/s)\|pq\|\Rightarrow \|pa\|<\|pq\|$ $\|bq\|\leqslant (2/s)\|pq\|\Rightarrow \|bq\|<\|pq\|$ $\|P_{pq}\|\leqslant t\|pa\|+\|ab\|+t\|bq\|$ Från Lemma 1 och 2 får vi: ${\begin{aligned}\|P_{pq}\|&\leqslant t(2/s)\|pq\|+(1+4/s)\|pq\|+t(2/s)\|pq\|\\ &=t(4/s)\|pq\|+(1+4/s)\|pq\|\\&=\left({\frac {4t+4}{s}}\right)\|pq\|+\|pq \|\\&=\left({\frac {4(t+1)}{s}}+1\right)\|pq\|\end{aligned}}$ Så att: ${\begin{aligned}t&={\frac {4(t+1)}{s}}+1\\t-1&={\frac {4(t+1)}{s}}\ \s(t-1)&=4(t+1)\\s(t-1)-4(t+1)&=0\\st-s-4t-4&=0\\t(s- 4)-s-4&=0\\t(s-4)&=s+4\\t&={\frac {s+4}{s-4}}\end{aligned}}$ Och så, om och , då har vi ett -skelett för uppsättningen poäng . $t=(s+4)/(s-4)$ $s>4$ $t$ $S$

Bevis på algoritmens riktighet [9]

Vi behöver dessa två WSPD-egenskaper

Lemma 1 : Låta vara en helt separerad sönderdelning av par med avseende på . Låt och . Sedan . $\{A,B\}$ $s$ $p,p'\in A$ $q\in B$ $|pp'|\leqslant (2/s)|pq|$

Lemma 2 : Låta vara en helt separerad sönderdelning av par med avseende på . Låt och . Sedan, . $\{A,B\}$ $s$ $p,p'\in A$ $q,q'\in B$ $|p'q'|\leqslant (1+4/s)|pq|$

Låta vara en väl separerad nedbrytning av par med avseende på i WSPD. Låt vara en kant som förbinder med . Låt det finnas en punkt och en punkt . Enligt WSPD-definitionen räcker det att kontrollera att det finns en -backbone path, eller -path för kort, mellan och , som vi betecknar med . Låt oss beteckna väglängden med . $\{A,B\}$ $s$ $[a,b]$ $A$ $B$ $p\in A$ $q\in B$ $t$ $t$ $sid$ $q$ $P_{pq}$ $P_{pq}$ $|P_{pq}|$

Antag att det finns en -bana mellan valfritt par av punkter med ett avstånd mindre än eller lika med och . Från triangelns olikhet, antaganden och det faktum att, och enligt Lemma 1, har vi: $t$ $|pq|$ $s>2$ $|pa|\leqslant (2/s)|pq|\Rightarrow |pa|<|pq|$ $|bq|\leqslant (2/s)|pq|\Rightarrow |bq|<|pq|$

$|P_{pq}|\leqslant t|pa|+|ab|+t|bq|$

Från Lemma 1 och 2 får vi:

${\begin{aligned}|P_{pq}|&\leqslant t(2/s)|pq|+(1+4/s)|pq|+t(2/s)|pq|\\ &=t(4/s)|pq|+(1+4/s)|pq|\\&=\left({\frac {4t+4}{s}}\right)|pq|+|pq |\\&=\left({\frac {4(t+1)}{s}}+1\right)|pq|\end{aligned}}$

Så att:

${\begin{aligned}t&={\frac {4(t+1)}{s}}+1\\t-1&={\frac {4(t+1)}{s}}\ \s(t-1)&=4(t+1)\\s(t-1)-4(t+1)&=0\\st-s-4t-4&=0\\t(s- 4)-s-4&=0\\t(s-4)&=s+4\\t&={\frac {s+4}{s-4}}\end{aligned}}$

Och så, om och , då har vi ett -skelett för uppsättningen poäng . $t=(s+4)/(s-4)$ $s>4$ $t$ $S$

Enligt beviset kan man ha ett godtyckligt värde för genom att uttrycka från , vilket ger . $t$ $s$ $t=(s+4)/(s-4)$ $s=4(t+1)/(t-1)$

Anteckningar

↑ Narasimhan, Smid, 2007 .
↑ Chew, 1986 , sid. 169–177.
↑ Klein och Kutz, 2007 , sid. 196–207.
↑ Althöfer, Das, Dobkin, Joseph, Soares, 1993 , sid. 81–100.
↑ Bose, Carmi, Farshi, Maheshwari, Smid, 2010 , sid. 711–729.
↑ Keil och Gutwin 1992 , sid. 13–28.
↑ Bose, Devroye, Loeffler, Snoeyink, Verma, 2009 , sid. 165–167.
↑ Callahan, Kosaraju, 1995 , sid. 67–90.
↑ Callahan, Kosaraju, 1993 , sid. 291–300.

Litteratur

L. Paul Chew. Det finns en plan graf nästan lika bra som hela grafen // Proc. Andra årliga symposiet om beräkningsgeometri. - 1986. - doi : 10.1145/10515.10534 .
Rolf Klein, Martin Kutz. Att beräkna geometriska minimumdilatationsgrafer är NP-Hård // Proc. 14th International Symposium in Graph Drawing , Karlsruhe, Tyskland, 2006 / Michael Kaufmann, Dorothea Wagner. - Springer Verlag , 2007. - T. 4372. - ( Lecture Notes in Computer Science ). — ISBN 978-3-540-70903-9 . - doi : 10.1007/978-3-540-70904-6 .
Paul B. Callahan, S. Rao Kosaraju. Snabbare algoritmer för vissa geometriska grafproblem i högre dimensioner // Proceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms . - Austin, Texas, USA: Society for Industrial and Applied Mathematics, 1993. - (SODA '93). - ISBN 0-89871-313-7 . - doi : 10.1145/313559.313777 .
Althöfer I., Das G., Dobkin DP, Joseph D., Soares J. Om glesa skiftnycklar av viktade grafer. // Diskret & beräkningsgeometri. - 1993. - T. 9 . - doi : 10.1007/bf02189308 .
Bose P., Carmi P., Farshi M., Maheshwari A., Smid. M. Beräkna den giriga nyckeln i nästan kvadratisk tid // Algorithmica. - 2010. - T. 58 . - doi : 10.1007/s00453-009-9293-4 .
Keil JM, Gutwin CA Klasser av grafer som approximerar den fullständiga euklidiska grafen // Discrete and Computational Geometry . - 1992. - T. 7 , nummer. 1 . - doi : 10.1007/BF02187821 .
Prosenjit Bose, Luc Devroye, Maarten Loeffler, Jack Snoeyink, Vishal Verma. Spännvidden för Delaunay-trianguleringen är större än $\scriptstyle {\pi /2}$ // Canadian Conference on Computational Geometry . — Vancouver, 2009.
Callahan PB, Kosaraju SR En nedbrytning av flerdimensionella punktuppsättningar med tillämpningar till k-närmaste grannar och n-kroppspotentialfält // Journal of the ACM. - 1995. - Januari ( vol. 42 , nummer 1 ). doi : 10.1145 / 200836.200853 .
Giri Narasimhan, Michiel Smid. Geometriska nyckelnätverk . - Cambridge University Press , 2007. - ISBN 0-521-81513-4 .