Geometrisk ramme

Geometrisk skruenøgle eller t - spændende graf eller t - spændende graf blev oprindeligt introduceret som en vægtet graf på et sæt punkter som hjørner, for hvilke der er en t - sti mellem ethvert par af hjørner for en fast parameter t . En t -sti er defineret som en sti i en graf med en vægt, der ikke overstiger t gange den rumlige afstand mellem endepunkterne. Parameteren t kaldes skelettets strækfaktor [ [1] .

I beregningsgeometri blev konceptet først diskuteret af L.P. Chu i 1986 [2] , selvom udtrykket "skruenøgle" (skelet) ikke blev nævnt i artiklen.

Konceptet med at spænde træer er kendt i grafteori - t - skeletter, disse er spændende undergrafer af grafer med lignende strækkeegenskaber, hvor afstanden mellem grafens hjørner er defineret ud fra grafteori. Derfor er geometriske spændingstræer spændende træer af komplette grafer indlejret i planet , hvor vægten af kanterne er lig med afstandene mellem hjørnerne i den tilsvarende metriske.

Skeletter kan bruges i beregningsgeometri til at løse nogle nærhedsproblemer . De finder også applikationer inden for andre områder såsom trafikplanlægning , kommunikationsnetværk - netværkspålidelighed, roamingoptimering i mobilnetværk osv.

Forskellige rygrader og kvalitetsmålinger

Der er forskellige mål, der bruges til at analysere kvaliteten af kernerne. De mest almindelige mål er antallet af kanter, den samlede vægt og den maksimale grad af toppunkter. De asymptotisk optimale værdier for disse mål er kanterne, den samlede vægt og den maksimale grad (hvor MST betyder vægten af det mindste spændingstræ ). $På)$ $O(MST)$ $O(1)$

Det er kendt, at det er et NP-hårdt problem at finde et spændende træ i det euklidiske plan med minimal strækning i n punkter med højst m kanter [3] .

Der er mange algoritmer, der fungerer godt under forskellige kvalitetsmålinger. Hurtige algoritmer inkluderer veladskilte parnedbrydning ( ) og theta-grafer , som bygger spænder med et lineært antal kanter i tid . Hvis der kræves bedre toppunktsvægte og grader, beregnes den grådige spænding i næsten kvadratisk tid. $O(n\log n)$

Theta graf

Theta-graf eller -graf tilhører familien af spændinger baseret på en kegle. Den vigtigste konstruktionsmetode er at opdele rummet omkring hvert vertex i mange kegler (en flad kegle er to stråler, det vil sige en vinkel), der adskiller de resterende hjørner af grafen. Ligesom Yao-graferne indeholder -grafen højst én kant til en kegle. Fremgangsmåden adskiller sig i den måde, kanter vælges på. Mens Yao-grafer vælger det nærmeste toppunkt i henhold til den metriske afstand i grafen, bestemmer -grafen en fast stråle indeholdt i hver kegle (normalt keglens halveringslinje) og vælger de nærmeste naboer (dvs. dem, der har den mindste afstand til strålen) . $\Theta$ $\Theta$ $\Theta$

Grådigt skelet

Et grådigt spændingstræ eller en grådig graf er defineret som en graf opnået ved gentagne gange at tilføje en kant mellem punkter, der ikke har en t -sti. Algoritmer til beregning af denne graf omtales som grådige spændingsalgoritmer. Det følger trivielt af konstruktionen, at grådige grafer er t -skeletter.

Den grådige kerne blev opdaget selvstændigt i 1989 af Althöfer [4] og Bern (upubliceret).

Det grådige skelet opnår det asymptotisk optimale antal kanter, totalvægt og maksimal toppunktsgrad og giver de bedste måleværdier i praksis. Det kan bygges i tid ved hjælp af plads [5] . $O(n^{2}\log n)$ $O(n^{2})$

Delaunay-triangulering

Chus hovedresultat var, at der for et sæt punkter i et plan eksisterer en triangulering af disse sæt af punkter, således at der for alle to punkter er en sti langs kanterne af trianguleringen med en længde, der ikke overstiger den euklidiske afstand mellem de to punkter . Resultatet blev brugt i trafikplanlægningen til at finde en acceptabel tilnærmelse af den korteste vej blandt forhindringer. $\scriptstyle {\sqrt {1}}0$

Den bedst kendte øvre grænse for en Delaunay-triangulering er skelettet for dets hjørner [6] . Den nedre grænse er hævet fra til 1,5846 [7] . $\scriptstyle {(4{\sqrt {3}}/9)\pi }\approx 2{,}418$ $\scriptstyle {{\pi }/2}$

En godt adskilt dekomponering af par

Skelettet kan konstrueres ud fra en fuldstændig adskilt nedbrydning af par som følger. Vi bygger en graf med et sæt punkter som hjørner og for hvert par i WSPD tilføjer vi en kant fra et vilkårligt punkt til et vilkårligt punkt . Bemærk, at den resulterende graf har et lineært antal kanter, da WSPD har et lineært antal par [8] . $S$ $\{A,B\}$ $a\i A$ $b\i B$

Bevis for rigtigheden af algoritmen [9]
Vi har brug for disse to WSPD-egenskaber Lemma 1 : Lade være en fuldstændig adskilt nedbrydning af par med hensyn til . Lad og . Så . $\{A,B\}$ $s$ $p,p'\in A$ $q\in B$ $\|pp'\|\leqslant (2/s)\|pq\|$ Lemma 2 : Lade være en fuldstændig adskilt nedbrydning af par med hensyn til . Lad og . Så ,. $\{A,B\}$ $s$ $p,p'\in A$ $q,q'\in B$ $\|p'q'\|\leqslant (1+4/s)\|pq\|$ Lade være en godt adskilt nedbrydning af par med hensyn til i WSPD. Lad være en kant, der forbinder med . Lad der være et punkt og et punkt . Ifølge WSPD-definitionen er det tilstrækkeligt at kontrollere, at der er en -backbone path, eller -path for short, mellem og , som vi betegner med . Lad os betegne stiens længde med . $\{A,B\}$ $s$ $[a,b]$ $EN$ $B$ $p\in A$ $q\in B$ $t$ $t$ $s$ $q$ $P_{pq}$ $P_{pq}$ $\|P_{pq}\|$ Antag, at der er en -sti mellem ethvert par af punkter med en afstand mindre end eller lig med og . Fra trekanten ulighed, antagelser og det faktum, og ifølge 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\|$ Fra Lemma 1 og 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\|\\&=\venstre({\frac {4t+4}{s}}\right)\|pq\|+\|pq \|\\&=\left({\frac {4(t+1)}{s}}+1\right)\|pq\|\end{aligned}}$ Så det: ${\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}}$ Og så, hvis og , så har vi et -skelet for sættet af punkter . $t=(s+4)/(s-4)$ $s>4$ $t$ $S$

Bevis for rigtigheden af algoritmen [9]

Vi har brug for disse to WSPD-egenskaber

Lemma 1 : Lade være en fuldstændig adskilt nedbrydning af par med hensyn til . Lad og . Så . $\{A,B\}$ $s$ $p,p'\in A$ $q\in B$ $|pp'|\leqslant (2/s)|pq|$

Lemma 2 : Lade være en fuldstændig adskilt nedbrydning af par med hensyn til . Lad og . Så ,. $\{A,B\}$ $s$ $p,p'\in A$ $q,q'\in B$ $|p'q'|\leqslant (1+4/s)|pq|$

Lade være en godt adskilt nedbrydning af par med hensyn til i WSPD. Lad være en kant, der forbinder med . Lad der være et punkt og et punkt . Ifølge WSPD-definitionen er det tilstrækkeligt at kontrollere, at der er en -backbone path, eller -path for short, mellem og , som vi betegner med . Lad os betegne stiens længde med . $\{A,B\}$ $s$ $[a,b]$ $EN$ $B$ $p\in A$ $q\in B$ $t$ $t$ $s$ $q$ $P_{pq}$ $P_{pq}$ $|P_{pq}|$

Antag, at der er en -sti mellem ethvert par af punkter med en afstand mindre end eller lig med og . Fra trekanten ulighed, antagelser og det faktum, og ifølge 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|$

Fra Lemma 1 og 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|\\&=\venstre({\frac {4t+4}{s}}\right)|pq|+|pq |\\&=\left({\frac {4(t+1)}{s}}+1\right)|pq|\end{aligned}}$

Så det:

${\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}}$

Og så, hvis og , så har vi et -skelet for sættet af punkter . $t=(s+4)/(s-4)$ $s>4$ $t$ $S$

Ifølge beviset kan man have en vilkårlig værdi for ved at udtrykke fra , som giver . $t$ $s$ $t=(s+4)/(s-4)$ $s=4(t+1)/(t-1)$

Noter

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

Litteratur

L. Paul Chew. Der er en plan graf næsten lige så god som hele grafen // Proc. 2. årlige symposium om beregningsgeometri. - 1986. - doi : 10.1145/10515.10534 .
Rolf Klein, Martin Kutz. Beregning af geometriske minimumsdilatationsgrafer er 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. Hurtigere algoritmer til nogle geometriske grafproblemer i højere 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 sparsomme nøgler af vægtede grafer. // Diskret & beregningsgeometri. - 1993. - T. 9 . - doi : 10.1007/bf02189308 .
Bose P., Carmi P., Farshi M., Maheshwari A., Smid. M. Beregning af den grådige skruenøgle i næsten kvadratisk tid // Algorithmica. - 2010. - T. 58 . - doi : 10.1007/s00453-009-9293-4 .
Keil JM, Gutwin CA Klasser af grafer, som tilnærmer den komplette euklidiske graf // Diskret og beregningsgeometri . - 1992. - T. 7 , udg. 1 . - doi : 10.1007/BF02187821 .
Prosenjit Bose, Luc Devroye, Maarten Loeffler, Jack Snoeyink, Vishal Verma. Spændingsforholdet for Delaunay-trianguleringen er større end $\scriptstyle {\pi /2}$ // Canadian Conference on Computational Geometry . - Vancouver, 2009.
Callahan PB, Kosaraju SR En nedbrydning af multidimensionelle punktsæt med applikationer til k-nærmeste-naboer og n-kropspotentiale felter // Journal of the ACM. - 1995. - Januar ( bind 42 , hæfte 1 ). doi : 10.1145 / 200836.200853 .
Giri Narasimhan, Michiel Smid. Geometriske nøglenetværk . - Cambridge University Press , 2007. - ISBN 0-521-81513-4 .