Graficul Theta

Theta graph sau -graph este un fel de arbore geometric care se întinde , similar cu graficul Yao . Metoda de construcție de bază descompune spațiul din jurul fiecărui vârf într-un set de unghiuri , care, astfel, despart vârfurile rămase ale graficului. Ca și graficele Xo, graficul conține cel mult o muchie pe con [1] (pentru vârful ales), dar diferă în modul în care este aleasă muchia. În timp ce graficele Yao aleg cel mai apropiat vârf în funcție de metrica spațiului , $\Theta$ $\Theta$ $\Theta$ -graf definește o rază fixă conținută în fiecare con (de obicei se folosește bisectoarea unghiului) iar vecinul cel mai apropiat este ales în funcție de proiecția ortogonală pe această rază. Graficul rezultat arată câteva proprietăți frumoase ale graficului de întindere [2] .

$\Theta$ -graficele au fost descrise pentru prima dată de Clarkson [3] în 1987 și independent de Keil [4] în 1988.

Clădire

$\Theta$ -graficele sunt date de mai mulți parametri care determină construcția acestuia. Cel mai evident parametru este , care corespunde numărului de conuri identice care despart spațiul din jurul fiecărui vârf. În special, pentru vârful , conul poate fi reprezentat ca două raze infinite care emană din acest punct cu un unghi între ele. În ceea ce privește , putem marca aceste conuri în sensul acelor de ceasornic. Aceste conuri împart planul și, de asemenea, împart setul rămas de vârfuri ale graficului (presupunând o poziție comună a vârfurilor) în seturi din nou în raport cu punctul . Fiecare vârf al graficului are același număr de conuri de partiție în aceeași orientare și putem lua în considerare mulțimea de vârfuri care se încadrează în interiorul fiecărui con. $k$ $p$ $p$ $\theta =2\pi /k$ $p$ $C_{1}\dots C_{k}$ $V_{1}\dots V_{k},$ $p$

Considerăm un singur con și trebuie să specificăm o altă rază care provine din , pe care o vom denota . Pentru orice vârf din interiorul conului , luăm în considerare proiecția ortogonală a fiecărui punct pe rază . Fie că vârful are cea mai mică astfel de proiecție, apoi se adaugă o muchie graficului . Aceasta este principala diferență față de graficele Yao, care aleg întotdeauna vârful cel mai apropiat de acesta . În exemplul din figură, contele Yao ar include marginea . $p$ $l$ $V_i$ $v\in V_{i}$ $l$ $r$ $\{p,r\)$ $p$ $\{p,q\)$

Construirea unui -graf este posibilă cu ajutorul unei linii de măturare în timp [2] . $\Theta$ $O(n\log{n})$

Proprietăți

$\Theta$ -graficele arată unele proprietăți bune pentru arborele de întindere geometric .

Atunci când parametrul este o constantă, -graful este un arbore de acoperire rar. Fiecare con dă cel mult o muchie, majoritatea vârfurilor vor fi de grad scăzut, iar întregul grafic va avea cel mult muchii. $k$ $\Theta$ $k\cdot n=O(n)$

Factorul de întindere între oricare două puncte ale scheletului este definit ca raportul dintre distanța metrică și distanța de-a lungul scheletului (adică după marginile scheletului). Factorul de întindere al întregului schelet este egal cu factorul de întindere maxim pentru toate perechile de puncte. După cum sa menționat mai sus,, atunci, dacă,-graful are un factor de întindere care nu depășește [2] . Dacăbisectoarea este aleasă drept linie dreaptă pentru proiecția ortogonală în fiecare con, atunci pentrucoeficientul de întindere nu depășește [5] . $\theta =2\pi /k$ $k\geqslant 9$ $\Theta$ $1/(\cos \theta -\sin \theta )$ $l$ $k\geqslant 7$ $1/(1-2\sin(\pi /k))$

Pentru -graph formează un grafic al vecinilor cei mai apropiați . Este ușor de observat că graficul este conectat, deoarece fiecare vârf este conectat la ceva din stânga și ceva din dreapta, dacă există. Pentru [6] [7] , [8] și [5] se știe că -graful este conex. Există rezultate nepublicate care arată că -graphurile sunt conectate și pentru . Există multe rezultate care dau o limită superioară și/sau inferioară a factorului de întindere. $k=1$ $\Theta$ $k=2$ $k = 4$ $5$ $6$ $\geqslant 7$ $\Theta$ $\Theta$ $k = 3$

Dacă este par, putem crea o variantă a -grafului cunoscută sub numele de semi -graf , în care conurile sunt împărțite în seturi pare și impare și sunt luate în considerare doar muchiile din conurile pare (sau numai impare). Se știe că semigrafele au unele proprietăți foarte interesante. De exemplu, se știe că un semi -graf (și, prin urmare, un -graf, care este pur și simplu unirea a două semi -grafe complementare) sunt cu 2 zone [8] . $k$ $\Theta _{k)$ $\Theta _{k)$ $\Theta _{k)$ $\Theta _{6}$ $\Theta _{6}$ $\Theta _{6}$

Programe de desenare a graficelor Theta

Vezi și

Note

↑ Un con înseamnă în acest caz două raze care emană dintr-un punct, adică un unghi.
↑ 1 2 3 Narasimhan, Smid, 2007 .
↑ Clarkson, 1987 , p. 56–65.
↑ Keil, 1988 , p. 208–213.
↑ 1 2 Ruppert, Seidel, 1991 , p. 207–210.
↑ Barba, Bose, De Carufel, van Renssen, Verdonschot, 2013 , p. 109–120.
↑ Bose, Morin, van Renssen, Verdonschot, 2015 , p. 108–119.
↑ 1 2 Bonichon, Gavoille, Hanusse, Ilcinkas, 2010 , p. 266–278.

Literatură

Keil J. Aproximarea graficului euclidian complet // Scandinavian Workshop on Algorithm Theory (SWAT 88). - 1988. - T. 318. - (Lecture Notes in Computer Science (LNCS)).
Giri Narasimhan, Michiel Smid. Rețele de chei geometrice . - Cambridge University Press , 2007. - ISBN 0-521-81513-4 .
Clarkson K. Algoritmi de aproximare pentru planificarea mișcării pe calea cea mai scurtă // În Proceedings of the xineth annual ACM symposium on Theory of computing (STOC '87) / Alfred V. Aho (Ed.). — New York, NY, SUA: ACM, 1987.
Ruppert J., Seidel R. Aproximarea graficului euclidian complet d -dimensional // În Proc. a treia Canada. Conf. Calculator. Geom. — 1991.
Luis Barba, Prosenjit Bose, Jean-Lou De Carufel, André van Renssen, Sander Verdonschot. Pe factorul de întindere al graficului theta-4 // Algoritmi și structuri de date. - Heidelberg: Springer, 2013. - P. 109–120. — (Note de curs în Informatică). - doi : 10.1007/978-3-642-40104-6_10 .
Prosenjit Bose, Pat Morin, André van Renssen, Sander Verdonschot. Graficul θ 5 este o cheie // Geometrie computațională. - 2015. - T. 48 , nr. 2 . — p. 108–119 . - doi : 10.1016/j.comgeo.2014.08.005 . - arXiv : 1212.0570 .
Bonichon N., Gavoille C., Hanusse N., Ilcinkas D. Conexiuni între teta-grafuri, triangulații Delaunay și suprafețe ortogonale. // În Concepte teoretice grafice în informatică. — Berlin/Heidelberg: Springer, 2010. — p. 266–278.