Theta-kaavio

Theta-graafi tai -graafi on eräänlainen geometrinen virittävä puu , samanlainen kuin Yao-graafi . Peruskonstruktiomenetelmä jakaa jokaisen kärjen ympärillä olevan tilan joukoksi kulmia , jotka siten hajottavat graafin loput kärjet. Kuten Xo-graafit, myös graafi sisältää korkeintaan yhden reunan kartiota kohden [1] (valitulla kärjellä), mutta ne eroavat toisistaan reunan valintatavassa. Kun Yao-graafit valitsevat lähimmän kärjen avaruusmetriikan mukaan , $\Theta$ $\Theta$ $\Theta$ -graph määrittelee kiinteän säteen jokaiseen kartioon (yleensä käytetään kulman puolittajaa) ja lähin naapuri valitaan tälle säteelle ortogonaalisen projektion mukaan. Tuloksena oleva kaavio näyttää hienoja ulottuvan graafin ominaisuuksia [2] .

$\Theta$ -kaaviot kuvaili ensimmäisen kerran Clarkson [3] vuonna 1987 ja itsenäisesti Keil [4] vuonna 1988.

Rakentaminen

$\Theta$ -kaaviot annetaan useilla parametreilla, jotka määrittävät sen rakenteen. Ilmeisin parametri on , joka vastaa identtisten kartioiden määrää, jotka hajottavat tilan kunkin kärjen ympäriltä. Erityisesti kärjen kohdalla kartio voidaan esittää kahdeksi äärettömäksi säteeksi, jotka lähtevät tästä pisteestä ja joiden välillä on kulma . Suhteessa voimme merkitä nämä kartiot myötäpäivään. Nämä kartiot jakavat tason ja jakavat myös graafin loput kärkijoukot (olettaen , että kärkipisteet ovat yhteisen sijainnin ) joukoiksi jälleen pisteen suhteen . Kussakin graafin kärjessä on sama määrä osiokartioita samassa suunnassa, ja voimme tarkastella kunkin kartion sisälle osuvien kärkien joukkoa. $k$ $s$ $s$ $\theta =2\pi /k$ $s$ $C_{1}\dots C_{k}$ $V_{1}\dots V_{k},$ $s$

Tarkastellaan yksittäistä kartiota ja meidän on määritettävä toinen säde, joka tulee kohteesta , jota merkitsemme . Jokaisen kartion sisällä olevan kärjen kohdalla otetaan huomioon kunkin pisteen ortogonaalinen projektio säteeseen . Olkoon kärjellä pienin tällainen projektio, jolloin graafiin lisätään reuna . Tämä on tärkein ero Yao-kaavioista, jotka valitsevat aina sitä lähinnä olevan kärjen . Kuvan esimerkissä Count Yao sisältäisi reunan . $s$ $l$ $V_i$ ${\displaystyle v\in V_{i))$ $l$ $r$ ${\näyttötyyli \{p,r\))$ $s$ ${\näyttötyyli \{p,q\))$

Graafin rakentaminen on mahdollista ajassa pyyhkäisyviivan avulla [2] . $\Theta$ $O(n\log{n})$

Ominaisuudet

$\Theta$ -kaaviot näyttävät geometrisen virittävän puun hyviä ominaisuuksia .

Kun parametri on vakio, -graafi on harvaan virittävä puu. Jokainen kartio antaa korkeintaan yhden reunan, suurin osa pisteistä on matala-asteisia ja koko graafissa on korkeintaan reunoja. $k$ $\Theta$ $k\cdot n=O(n)$

Kahden luurankopisteen välinen venytyskerroin Koko luurangon venytyskerroin on yhtä suuri kuin kaikkien pisteparien suurin venytyskerroin. Kuten edellä mainittiin,, silloin, jos,-graafin venytyskerroin ei ylitä [2] . Jospuolittaja valitaan suoraksi linjaksi kohtisuoralle projektiolle kussakin kartiossa, niinvenytyskerroin ei ylitä [5] . $\theta =2\pi /k$ $k\geqslant 9$ $\Theta$ $1/(\cos \theta -\sin \theta )$ $l$ $k\geqslant 7$ $1/(1-2\sin(\pi /k))$

For -graph muodostaa kaavion lähimmistä naapureista . On helppo nähdä, että graafi on yhdistetty, koska jokainen kärki on kytketty johonkin vasemmalla ja johonkin oikealla, jos niitä on. Kohdille [6] [7] , [8] ja [5] tiedetään, että -graafi on yhdistetty. On julkaisemattomia tuloksia, jotka osoittavat, että -kaaviot ovat myös yhteydessä . On monia tuloksia, jotka antavat ylä- ja/tai alarajan venytystekijälle. $k = 1$ $\Theta$ $k = 2$ $k = 4$ $5$ $6$ $\geqslant 7$ $\Theta$ $\Theta$ $k = 3$

Jos se on parillinen, voimme luoda -graafista muunnelman , joka tunnetaan nimellä puoligraafi , jossa kartiot jaetaan parillisiin ja parittoihin ryhmiin ja huomioidaan vain parillisten (tai vain parittomien) kartioiden reunat. Puolikaavioilla tiedetään olevan joitain erittäin mielenkiintoisia ominaisuuksia. Esimerkiksi tiedetään, että puoligraafi (ja siten -graafi, joka on yksinkertaisesti kahden täydentävän puoligraafin liitto) on 2-alue [8] . $k$ ${\displaystyle \Theta _{k))$ ${\displaystyle \Theta _{k))$ ${\displaystyle \Theta _{k))$ $\Theta _{6}$ $\Theta _{6}$ $\Theta _{6}$

Theta-kaavion piirustusohjelmat

Katso myös

Muistiinpanot

↑ Kartio tarkoittaa tässä tapauksessa kahta sädettä, jotka lähtevät pisteestä eli kulmasta.
↑ 1 2 3 Narasimhan, Smid, 2007 .
↑ Clarkson, 1987 , s. 56–65.
↑ Keil, 1988 , s. 208–213.
↑ 1 2 Ruppert, Seidel, 1991 , s. 207–210.
↑ Barba, Bose, De Carufel, van Renssen, Verdonschot, 2013 , s. 109-120.
↑ Bose, Morin, van Renssen, Verdonschot, 2015 , s. 108-119.
↑ 1 2 Bonichon, Gavoille, Hanusse, Ilcinkas, 2010 , s. 266-278.

Kirjallisuus

Keil J. Täydellisen euklidisen graafin lähentäminen // Scandinavian Workshop on Algorithm Theory (SWAT 88). - 1988. - T. 318. - (Lecture Notes in Computer Science (LNCS)).
Giri Narasimhan, Michiel Smid. Geometriset avaimet . - Cambridge University Press , 2007. - ISBN 0-521-81513-4 .
Clarkson K. Approksimaatioalgoritmit lyhimmän polun liikkeen suunnitteluun // Proceedings of the yhdeksäntoista vuotuinen ACM symposium on Theory of Computing (STOC '87) / Alfred V. Aho (Toim.). - New York, NY, USA: ACM, 1987.
Ruppert J., Seidel R. Approximating the d - dimensional täydellinen Euklidinen graafi // In Proc. 3. Kanada. Conf. Comput. Geom. – 1991.
Luis Barba, Prosenjit Bose, Jean-Lou De Carufel, André van Renssen, Sander Verdonschot. Theta-4-graafin venytyskertoimesta // Algoritmit ja tietorakenteet. - Heidelberg: Springer, 2013. - P. 109–120. — (Luentomuistiinpanot tietojenkäsittelytieteestä). - doi : 10.1007/978-3-642-40104-6_10 .
Prosenjit Bose, Pat Morin, André van Renssen, Sander Verdonschot. θ 5 -kaavio on jakoavain // Computational Geometry. - 2015. - T. 48 , no. 2 . — s. 108–119 . - doi : 10.1016/j.comgeo.2014.08.005 . - arXiv : 1212.0570 .
Bonichon N., Gavoille C., Hanusse N., Ilcinkas D. Yhteydet theta-graafien, Delaunay-kolmioiden ja ortogonaalisten pintojen välillä. // Kirjassa Graafiteoreettiset käsitteet tietojenkäsittelytieteessä. — Berlin/Heidelberg: Springer, 2010. — s. 266–278.