Geometriai keret

A geometriai csavarkulcsot vagy t -feszítő gráfot , vagy t - feszítő gráfot eredetileg súlyozott gráfként vezették be olyan pontok halmazán, amelyeknél van egy t - útvonal bármely csúcspár között egy rögzített t paraméterhez . A t -útvonalat úgy definiáljuk, mint egy olyan utat a gráfban, amelynek súlya nem haladja meg a végpontok közötti térbeli távolság t -szeresét. A t paramétert a váz [1] nyújtási tényezőjének nevezzük .

A számítási geometriában a koncepciót először L.P. Chu 1986-ban [2] , bár a "kulcs" (csontváz) kifejezés nem szerepel a cikkben.

A feszítőfák fogalma a gráfelméletben ismert - t - vázak, ezek hasonló nyújtási tulajdonságú gráfok feszítő részgráfjai, ahol a gráf csúcsok közötti távolságot gráfelméletileg határozzák meg. Ezért a geometriai feszítőfák a síkba ágyazott teljes gráfok feszítőfái , amelyekben az élek súlya megegyezik a megfelelő metrika csúcsai közötti távolságokkal.

A csontvázak a számítási geometriában használhatók néhány közelségi probléma megoldására . Más területeken is találnak alkalmazást, mint például a forgalomtervezés , a kommunikációs hálózatok - hálózat megbízhatóság, a roaming optimalizálás mobilhálózatokban stb.

A minőség különféle gerincvonalai és mértékei

Különféle méréseket alkalmaznak a magok minőségének elemzésére. A leggyakoribb mérték az élek száma, a teljes súly és a csúcsok maximális foka . Ezen mértékek aszimptotikusan optimális értékei az élek, a teljes tömeg és a maximális fok (ahol az MST a minimális feszülőfa súlyát jelenti ). $Tovább)$ $O(MST)$ $O(1)$

Ismeretes, hogy egy feszítőfát találni az euklideszi síkban minimális nyújtással n pontban, legfeljebb m éllel NP-nehéz probléma [3] .

Számos olyan algoritmus létezik, amely jól teljesít a különböző minőségi mérőszámok mellett. A gyors algoritmusok közé tartozik a jól elválasztott párfelbontás ( ) és a thétagráfok , amelyek lineáris számú éllel készítenek átfeszítéseket időben . Ha jobb csúcssúlyokra és fokokra van szükség, akkor a mohó feszülést majdnem másodfokú idő alatt számítja ki. $O(n\log n)$

Théta gráf

A théta-gráf vagy -gráf a kúp alapú átfeszítések családjába tartozik. A szerkesztés fő módja az, hogy az egyes csúcsok körüli teret több kúpra osztjuk (a lapos kúp két sugár, azaz egy szög), amelyek elválasztják a gráf többi csúcsát. A Yao gráfokhoz hasonlóan a -gráf legfeljebb egy élt tartalmaz egy kúphoz. A megközelítés eltér az élek kiválasztásának módjától. Míg a Yao gráfok a gráf metrikus távolságának megfelelően választják ki a legközelebbi csúcsot, a -gráf meghatároz egy rögzített sugarat, amely minden kúpban található (általában a kúp felezőpontja), és kiválasztja a legközelebbi szomszédokat (azaz azokat, amelyek a legkisebb távolságra vannak a sugártól). . $\Theta$ $\Theta$ $\Theta$

Mohó csontváz

A mohó feszítőfát vagy a mohó gráfot úgy definiáljuk, mint egy olyan gráfot, amelyet úgy kapunk, hogy ismételten hozzáadunk egy élt olyan pontokhoz, amelyeknek nincs t - útvonala. A gráf kiszámítására szolgáló algoritmusokat mohó feszítő algoritmusoknak nevezzük. A konstrukcióból triviálisan következik, hogy a mohó gráfok t -csontvázak.

A kapzsi magot 1989-ben egymástól függetlenül fedezte fel Althöfer [4] és Bern (kiadatlan).

A mohó csontváz eléri az aszimptotikusan optimális élszámot, össztömeget és maximális csúcsfokot, és a gyakorlatban a legjobb mértékértékeket adja. A tér felhasználásával időben felépíthető [5] . $O(n^{2}\log n)$ $O(n^{2})$

Delaunay háromszögelés

Chu fő eredménye az volt, hogy egy síkban lévő ponthalmazra létezik egy háromszögelés ezeknek a ponthalmazoknak úgy, hogy bármely két pontban van egy olyan út a háromszögelés élei mentén, amelynek hossza nem haladja meg a két pont közötti euklideszi távolságot . . Az eredményt a forgalomtervezésben használták fel az akadályok közötti legrövidebb út elfogadható közelítésére. $\scriptstyle {\sqrt {1}}0$

A Delaunay-háromszögelés legismertebb felső korlátja a csúcsainak -váza [6] . Az alsó határt 1,5846-ra növelték [7] . $\scriptstyle {(4{\sqrt {3}}/9)\pi }\approx 2{,}418$ $\scriptstyle {{\pi }/2}$

A párok jól elkülöníthető bontása

párok teljesen elválasztott dekompozíciójából az alábbiak szerint lehet megszerkeszteni . Összeállítunk egy gráfot, amelyben csúcsokként pontok állnak, és a WSPD-ben minden párhoz hozzáadunk egy élt egy tetszőleges pontból egy tetszőleges ponthoz . Figyeljük meg, hogy a kapott gráfnak lineáris számú éle van, mivel a WSPD-nek lineáris számú párja van [8] . $S$ $\{A,B\}$ $a\in A$ $b\in B$

Az algoritmus helyességének bizonyítása [9]
Erre a két WSPD tulajdonságra van szükségünk 1. lemma : Legyen párok teljesen elválasztott dekompozíciója . Hagyjuk és . Akkor . $\{A,B\}$ $s$ $p,p'\in A$ $q\in B$ $\|pp'\|\leqslant (2/s)\|pq\|$ 2. lemma : Legyen párok teljesen elválasztott dekompozíciója . Hagyjuk és . Aztán, . $\{A,B\}$ $s$ $p,p'\in A$ $q,q'\in B$ $\|p'q'\|\leqslant (1+4/s)\|pq\|$ Legyen a párok jól elválasztott dekompozíciója a WSPD-ben. Legyen egy él összekötő . Legyen egy pont és egy pont . A WSPD definíciója szerint elegendő ellenőrizni, hogy van-e -gerincútvonal, vagy röviden -útvonal a és között , amit -vel jelölünk . Jelöljük az út hosszát -vel . $\{A,B\}$ $s$ $[a,b]$ $A$ $B$ $p\in A$ $q\in B$ $t$ $t$ $p$ $q$ $P_{pq}$ $P_{pq}$ $\|P_{pq}\|$ Tegyük fel, hogy van egy -útvonal bármely olyan pontpár között, amelyek távolsága kisebb vagy egyenlő, mint és . A háromszög egyenlőtlenségből, a feltevésekből és abból a tényből, hogy az 1. lemma szerint a következőket kapjuk: $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\|$ Az 1. és 2. lemmából a következőket kapjuk: ${\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{igazított}}$ Tehát, hogy: ${\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{igazított}}$ Tehát, ha és , akkor van egy -csontvázunk a ponthalmazhoz . $t=(s+4)/(s-4)$ $s>4$ $t$ $S$

Az algoritmus helyességének bizonyítása [9]

Erre a két WSPD tulajdonságra van szükségünk

1. lemma : Legyen párok teljesen elválasztott dekompozíciója . Hagyjuk és . Akkor . $\{A,B\}$ $s$ $p,p'\in A$ $q\in B$ $|pp'|\leqslant (2/s)|pq|$

2. lemma : Legyen párok teljesen elválasztott dekompozíciója . Hagyjuk és . Aztán, . $\{A,B\}$ $s$ $p,p'\in A$ $q,q'\in B$ $|p'q'|\leqslant (1+4/s)|pq|$

Legyen a párok jól elválasztott dekompozíciója a WSPD-ben. Legyen egy él összekötő . Legyen egy pont és egy pont . A WSPD definíciója szerint elegendő ellenőrizni, hogy van-e -gerincútvonal, vagy röviden -útvonal a és között , amit -vel jelölünk . Jelöljük az út hosszát -vel . $\{A,B\}$ $s$ $[a,b]$ $A$ $B$ $p\in A$ $q\in B$ $t$ $t$ $p$ $q$ $P_{pq}$ $P_{pq}$ $|P_{pq}|$

Tegyük fel, hogy van egy -útvonal bármely olyan pontpár között, amelyek távolsága kisebb vagy egyenlő, mint és . A háromszög egyenlőtlenségből, a feltevésekből és abból a tényből, hogy az 1. lemma szerint a következőket kapjuk: $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|$

Az 1. és 2. lemmából a következőket kapjuk:

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

Tehát, hogy:

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

Tehát, ha és , akkor van egy -csontvázunk a ponthalmazhoz . $t=(s+4)/(s-4)$ $s>4$ $t$ $S$

A bizonyítás szerint tetszőleges értéke lehet a -ból való kifejezéssel , ami megadja . $t$ $s$ $t=(s+4)/(s-4)$ $s=4(t+1)/(t-1)$

Jegyzetek

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

Irodalom

L. Paul Chew. Van egy sík gráf, amely majdnem olyan jó, mint a teljes gráf // Proc. 2. éves szimpózium a számítási geometriáról. - 1986. - doi : 10.1145/10515.10534 .
Rolf Klein, Martin Kutz. A geometriai minimális dilatációs grafikonok kiszámítása NP-nehéz // Proc. 14th International Symposium in Graph Drawing , Karlsruhe, Németország, 2006 / Michael Kaufmann, Dorothea Wagner. - Springer Verlag , 2007. - T. 4372. - ( Számítástechnikai előadásjegyzetek ). — ISBN 978-3-540-70903-9 . - doi : 10.1007/978-3-540-70904-6 .
Paul B. Callahan, S. Rao Kosaraju. Gyorsabb algoritmusok egyes geometriai gráfproblémákhoz nagyobb dimenziókban // Proceedings of the Fourth Annual 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. On sparse spanners of weighted graphs. // Diszkrét és számítási geometria. - 1993. - T. 9 . - doi : 10.1007/bf02189308 .
Bose P., Carmi P., Farshi M., Maheshwari A., Smid. M. A mohó villáskulcs számítása közel másodfokú időben // Algorithmica. - 2010. - T. 58 . - doi : 10.1007/s00453-009-9293-4 .
Keil JM, Gutwin CA A teljes euklideszi gráfot közelítő gráfok osztályai // Discrete and Computational Geometry . - 1992. - T. 7 , szám. 1 . - doi : 10.1007/BF02187821 .
Prosenjit Bose, Luc Devroye, Maarten Loeffler, Jack Snoeyink, Vishal Verma. A Delaunay-háromszögelés feszítési aránya nagyobb, mint $\scriptstyle {\pi /2}$ // Canadian Conference on Computational Geometry . - Vancouver, 2009.
Callahan PB, Kosaraju SR Többdimenziós ponthalmazok bontása k-legközelebbi szomszédokra és n-test potenciálmezőkre történő alkalmazásokkal // Journal of the ACM. - 1995. - január ( 42. évf. , 1. szám ). doi : 10.1145 / 200836.200853 .
Giri Narasimhan, Michiel Smid. Geometrikus villáskulcs-hálózatok . - Cambridge University Press , 2007. - ISBN 0-521-81513-4 .