Theta graf

Theta-graf eller -graf er en slags geometrisk spændingstræ , der ligner Yao-grafen . Den grundlæggende konstruktionsmetode opdeler rummet omkring hvert toppunkt i et sæt vinkler , som derved opdeler de resterende hjørner af grafen. Ligesom Xo-graferne indeholder grafen højst én kant pr. kegle [1] (for det valgte toppunkt), men de adskiller sig i den måde, kanten er valgt. Mens Yao-grafer vælger det nærmeste toppunkt i henhold til rummetrikken , bestemmer -grafen en fast stråle indeholdt i hver kegle (normalt bruges vinkelhalveringslinjen) og vælger den nærmeste nabo i henhold til den ortogonale projektion på den stråle. Den resulterende graf viser nogle flotte spændende grafegenskaber [2] . $\Theta$ $\Theta$ $\Theta$

$\Theta$ -grafer blev først beskrevet af Clarkson [3] i 1987 og uafhængigt af Keil [4] i 1988.

Konstruktion

$\Theta$ -grafer er givet af flere parametre, der bestemmer dens konstruktion. Den mest oplagte parameter er , som svarer til antallet af identiske kegler, der opdeler rummet omkring hvert vertex. Især for toppunktet kan keglen af repræsenteres som to uendelige stråler, der udgår fra dette punkt med en vinkel imellem dem. Med hensyn til vi kan markere disse kegler som med uret. Disse kegler opdeler planet, og deler også det resterende sæt af hjørner af grafen (forudsat en fælles position af hjørnerne) i sæt igen i forhold til punktet . Hvert toppunkt på grafen har det samme antal partitionskegler i samme orientering, og vi kan overveje det sæt af toppunkter, der falder inden for hver kegle. $k$ $s$ $s$ $\theta =2\pi /k$ $s$ $C_{1}\dots C_{k}$ $V_{1}\dots V_{k},$ $s$

Overvej en enkelt kegle, og vi skal angive en anden stråle, der kommer fra , som vi vil betegne . For ethvert toppunkt inde i keglen betragter vi den ortogonale projektion af hvert punkt på strålen . Lad toppunktet have den mindste projektion, så tilføjes en kant til grafen . Dette er den største forskel fra Yao-graferne, som altid vælger det toppunkt , der er tættest på . I eksemplet i figuren ville Count Yao inkludere kanten . $s$ $l$ $V_i$ ${\displaystyle v\in V_{i))$ $l$ $r$ ${\displaystyle \{p,r\))$ $s$ ${\displaystyle \{p,q\))$

Konstruktionen af en -graf er mulig ved hjælp af en fejende linje i tiden [2] . $\Theta$ $O(n\log{n})$

Egenskaber

$\Theta$ -grafer viser nogle gode egenskaber for det geometriske spændingstræ .

Når parameteren er en konstant, er -grafen et sparsomt spændingstræ. Hver kegle giver højst én kant, de fleste af hjørnerne vil være af lav grad, og hele grafen vil højst have kanter. $k$ $\Theta$ $k\cdot n=O(n)$

Strækfaktoren mellem to skeletpunkter er defineret som forholdet mellem den metriske afstand og afstanden langs skelettet (det vil sige at følge skelettets kanter). Strækfaktoren for hele skelettet er lig med den maksimale strækfaktor for alle pointpar. Som nævnt ovenfor,, så hvis,-grafen har en strækfaktor, der ikke overstiger [2] . Hvishalveringslinjen vælges som en ret linje for den ortogonale projektion i hver kegle, såoverstiger strækningskoefficienten ikke [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 -graf danner en graf over nærmeste naboer . Det er let at se, at grafen hænger sammen, da hvert hjørne er forbundet med noget til venstre og noget til højre, hvis de findes. For [6] [7] , [8] og [5] er det kendt, at -grafen er forbundet. Der er upublicerede resultater, der viser, at -grafer også er forbundet for . Der er mange resultater, der giver en øvre og/eller nedre grænse for strækfaktoren. $k=1$ $\Theta$ $k=2$ $k = 4$ $5$ $6$ $\geqslant 7$ $\Theta$ $\Theta$ $k = 3$

Hvis det er lige, kan vi lave en variant af -grafen kendt som en semi -graf , hvor keglerne er opdelt i lige og ulige sæt, og kun kanter i lige (eller kun ulige) kegler tages i betragtning. Halvgrafer er kendt for at have nogle meget interessante egenskaber. For eksempel er det kendt, at en semi - graf (og dermed en -graf, som blot er foreningen af to komplementære semi -grafer) er 2-areal [8] . $k$ ${\displaystyle \Theta _{k))$ ${\displaystyle \Theta _{k))$ ${\displaystyle \Theta _{k))$ $\Theta _{6}$ $\Theta _{6}$ $\Theta _{6}$

Theta graf tegneprogrammer

Se også

Noter

↑ En kegle betyder i dette tilfælde to stråler, der udgår fra et punkt, det vil sige en vinkel.
↑ 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.

Litteratur

Keil J. Approximating the complete Euclidean graph // Scandinavian Workshop on Algorithm Theory (SWAT 88). - 1988. - T. 318. - (Lecture Notes in Computer Science (LNCS)).
Giri Narasimhan, Michiel Smid. Geometriske nøglenetværk . - Cambridge University Press , 2007. - ISBN 0-521-81513-4 .
Clarkson K. Approximationsalgoritmer til planlægning af korteste vejbevægelse // I Proceedings of the nittende årlige ACM symposium on Theory of computing (STOC '87) / Alfred V. Aho (Ed.). — New York, NY, USA: ACM, 1987.
Ruppert J., Seidel R. Tilnærmelse af den d -dimensionelle komplette euklidiske graf // In Proc. 3. Canada. Konf. Comput. Geom. – 1991.
Luis Barba, Prosenjit Bose, Jean-Lou De Carufel, André van Renssen, Sander Verdonschot. Om strækfaktoren for theta-4-grafen // Algoritmer og datastrukturer. - Heidelberg: Springer, 2013. - S. 109–120. — (Forelæsningsnotater i datalogi). - doi : 10.1007/978-3-642-40104-6_10 .
Prosenjit Bose, Pat Morin, André van Renssen, Sander Verdonschot. θ 5 -grafen er en skruenøgle // 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. Forbindelser mellem theta-grafer, Delaunay-trianguleringer og ortogonale overflader. // I grafteoretiske begreber i datalogi. — Berlin/Heidelberg: Springer, 2010. — s. 266–278.