Cadru geometric

Cheie geometrică sau graficul t - spanning sau graficul t - spanning a fost introdus inițial ca un grafic ponderat pe un set de puncte ca vârfuri, pentru care există o cale t între orice pereche de vârfuri pentru un parametru fix t . O cale t este definită ca o cale într-un grafic cu o pondere care nu depășește de t ori distanța spațială dintre punctele terminale. Parametrul t se numește factor de întindere scheletului [1] .

În geometria computațională, conceptul a fost discutat pentru prima dată de L.P. Chu în 1986 [2] , deși termenul „cheie” (schelet) nu a fost menționat în articol.

Conceptul de arbori de întindere este cunoscut în teoria grafurilor - t - schelete, acestea sunt subgrafe de întindere ale grafurilor cu proprietăți de întindere similare, unde distanța dintre vârfurile grafurilor este definită în termeni de teoria grafurilor. Prin urmare, arborii de întindere geometrici sunt arbori de întindere ai graficelor complete încorporate în plan , în care greutățile muchiilor sunt egale cu distanțele dintre vârfurile din metrica corespunzătoare.

Scheletele pot fi folosite în geometria computațională pentru a rezolva unele probleme de proximitate . De asemenea, găsesc aplicații în alte domenii precum planificarea traficului , rețelele de comunicații - fiabilitatea rețelei, optimizarea roamingului în rețelele mobile etc.

Diferite coloane vertebrale și măsuri de calitate

Există diferite măsuri utilizate pentru a analiza calitatea miezurilor. Cele mai comune măsuri sunt numărul de muchii, greutatea totală și gradul maxim al vârfurilor. Valorile optime asimptotic pentru aceste măsuri sunt marginile, greutatea totală și gradul maxim (unde MST înseamnă greutatea arborelui de acoperire minim ). $Pe)$ $O(MST)$ $O(1)$

Se știe că găsirea unui arbore spanning în planul euclidian cu întindere minimă în n puncte cu cel mult m muchii este o problemă NP-hard [3] .

Există mulți algoritmi care funcționează bine sub diferite măsuri de calitate. Algoritmii rapidi includ descompunerea perechilor bine separate ( ) și graficele theta , care construiesc întinderi cu un număr liniar de muchii în timp . Dacă sunt necesare greutăți și grade de vârf mai bune, întinderea lacomă este calculată în timp aproape pătratic. $O(n\log n)$

Graficul Theta

Theta-graph sau -graph aparține familiei de întinderi bazate pe un con. Principala metodă de construcție este împărțirea spațiului din jurul fiecărui vârf în mai multe conuri (un con plat este două raze, adică un unghi) care separă vârfurile rămase ale graficului. Ca și graficele Yao , -graful conține cel mult o muchie pentru un con. Abordarea diferă în modul în care sunt selectate marginile. În timp ce graficele Yao aleg cel mai apropiat vârf în funcție de distanța metrică din grafic, graficul - determină o rază fixă conținută în fiecare con (de obicei bisectoarea conului) și alege cei mai apropiați vecini (adică cei care au cea mai mică distanță față de rază) . $\Theta$ $\Theta$ $\Theta$

Schelet lacom

Un arbore spanning greedy sau un grafic greedy este definit ca un grafic obținut prin adăugarea în mod repetat a unei margini între punctele care nu au o cale t . Algoritmii pentru calcularea acestui grafic sunt denumiți algoritmi greedy spanning. Din construcție rezultă trivial că graficele lacome sunt schelete t .

Miezul lacom a fost descoperit independent în 1989 de către Althöfer [4] și Bern (nepublicat).

Scheletul lacom realizează numărul optim asimptotic de muchii, greutatea totală și gradul maxim de vârf și oferă cele mai bune valori de măsură în practică. Poate fi construit în timp folosind spațiu [5] . $O(n^{2}\log n)$ $O(n^{2})$

Triangulație Delaunay

Principalul rezultat al lui Chu a fost că pentru un set de puncte dintr-un plan există o triangulare a acestor seturi de puncte astfel încât pentru oricare două puncte există o cale de-a lungul marginilor triangulației cu o lungime care nu depășește distanța euclidiană dintre cele două puncte. . Rezultatul a fost folosit în planificarea traficului pentru a găsi o aproximare acceptabilă a drumului cel mai scurt dintre obstacole. $\scriptstyle {\sqrt {1}}0$

Cea mai cunoscută limită superioară pentru o triangulație Delaunay este scheletul pentru vârfurile sale [6] . Limita inferioară a fost mărită de la 1,5846 [7] . $\scriptstyle {(4{\sqrt {3}}/9)\pi }\approx 2{,}418$ $\scriptstyle {{\pi }/2}$

O descompunere bine separată de perechi

Scheletul poate fi construit dintr-o descompunere complet separată de perechi , după cum urmează. Construim un grafic cu un set de puncte ca vârfuri și pentru fiecare pereche în WSPD adăugăm o muchie de la un punct arbitrar la un punct arbitrar . Rețineți că graficul rezultat are un număr liniar de muchii, deoarece WSPD are un număr liniar de perechi [8] . $S$ $\{A,B\}$ $a\în A$ $b\în B$

Dovada corectitudinii algoritmului [9]
Avem nevoie de aceste două proprietăți WSPD Lema 1 : Fie o descompunere complet separată de perechi în raport cu . Lasă și . Apoi . $\{A,B\}$ $s$ $p,p'\in A$ $q\in B$ $\|pp'\|\leqslant (2/s)\|pq\|$ Lema 2 : Fie o descompunere complet separată de perechi în raport cu . Lasă și . Apoi, . $\{A,B\}$ $s$ $p,p'\in A$ $q,q'\in B$ $\|p'q'\|\leqslant (1+4/s)\|pq\|$ Fie o descompunere bine separată de perechi în raport cu în WSPD. Să fie o margine care se conectează cu . Să fie un punct și un punct . Conform definiției WSPD, este suficient să verificăm dacă există o cale -backbone, sau -path pentru scurt, între și , pe care o notăm cu . Să notăm lungimea căii cu . $\{A,B\}$ $s$ $[a,b]$ $A$ $B$ $p\in A$ $q\in B$ $t$ $t$ $p$ $q$ $P_{pq}$ $P_{pq}$ $\|P_{pq}\|$ Să presupunem că există o cale între orice pereche de puncte cu o distanță mai mică sau egală cu și . Din inegalitatea triunghiului, ipoteze și faptul că, și conform Lemei 1, avem: $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\|$ Din lema 1 și 2 obținem: ${\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{aliniat}}$ Astfel încât: ${\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}}$ Și așa, dacă și , atunci avem un -schelet pentru mulțimea de puncte . $t=(s+4)/(s-4)$ $s>4$ $t$ $S$

Dovada corectitudinii algoritmului [9]

Avem nevoie de aceste două proprietăți WSPD

Lema 1 : Fie o descompunere complet separată de perechi în raport cu . Lasă și . Apoi . $\{A,B\}$ $s$ $p,p'\in A$ $q\in B$ $|pp'|\leqslant (2/s)|pq|$

Lema 2 : Fie o descompunere complet separată de perechi în raport cu . Lasă și . Apoi, . $\{A,B\}$ $s$ $p,p'\in A$ $q,q'\in B$ $|p'q'|\leqslant (1+4/s)|pq|$

Fie o descompunere bine separată de perechi în raport cu în WSPD. Să fie o margine care se conectează cu . Să fie un punct și un punct . Conform definiției WSPD, este suficient să verificăm dacă există o cale -backbone, sau -path pentru scurt, între și , pe care o notăm cu . Să notăm lungimea căii cu . $\{A,B\}$ $s$ $[a,b]$ $A$ $B$ $p\in A$ $q\in B$ $t$ $t$ $p$ $q$ $P_{pq}$ $P_{pq}$ $|P_{pq}|$

Să presupunem că există o cale între orice pereche de puncte cu o distanță mai mică sau egală cu și . Din inegalitatea triunghiului, ipoteze și faptul că, și conform Lemei 1, avem: $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|$

Din lema 1 și 2 obținem:

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

Astfel încât:

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

Și așa, dacă și , atunci avem un -schelet pentru mulțimea de puncte . $t=(s+4)/(s-4)$ $s>4$ $t$ $S$

Conform dovezii, se poate avea o valoare arbitrară pentru exprimând din , ceea ce dă . $t$ $s$ $t=(s+4)/(s-4)$ $s=4(t+1)/(t-1)$

Note

↑ Narasimhan, Smid, 2007 .
↑ Chew, 1986 , p. 169–177.
↑ Klein și 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 și 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.

Literatură

L. Paul Chew. Există un grafic plan aproape la fel de bun ca și graficul complet // Proc. Al 2-lea simpozion anual de geometrie computațională. - 1986. - doi : 10.1145/10515.10534 .
Rolf Klein, Martin Kutz. Calcularea graficelor geometrice de dilatație minimă este NP-Hard // Proc. 14th International Symposium in Graph Drawing , Karlsruhe, Germania, 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. Algoritmi mai rapidi pentru unele probleme de grafice geometrice în dimensiuni mai mari // Proceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms . - Austin, Texas, SUA: 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. // Geometrie discretă și computațională. - 1993. - T. 9 . - doi : 10.1007/bf02189308 .
Bose P., Carmi P., Farshi M., Maheshwari A., Smid. M. Calcularea cheii lacome în timp aproape pătratic // Algorithmica. - 2010. - T. 58 . - doi : 10.1007/s00453-009-9293-4 .
Keil JM, Gutwin CA Clase de grafice care aproximează graficul euclidian complet // Geometrie discretă și computațională . - 1992. - T. 7 , nr. 1 . - doi : 10.1007/BF02187821 .
Prosenjit Bose, Luc Devroye, Maarten Loeffler, Jack Snoeyink, Vishal Verma. Raportul de acoperire al triangulației Delaunay este mai mare decât $\scriptstyle {\pi /2}$ // Canadian Conference on Computational Geometry . — Vancouver, 2009.
Callahan PB, Kosaraju SR O descompunere a seturilor de puncte multidimensionale cu aplicații la k-nearest-neighbors și n-Body Potential Fields // Journal of the ACM. - 1995. - ianuarie ( vol. 42 , numărul 1 ). doi : 10.1145 / 200836.200853 .
Giri Narasimhan, Michiel Smid. Rețele de chei geometrice . - Cambridge University Press , 2007. - ISBN 0-521-81513-4 .