Theta graf

Theta-grafen eller -grafen är ett slags geometriskt spännande träd , liknande Yao-grafen . Den grundläggande konstruktionsmetoden delar upp utrymmet runt varje vertex i en uppsättning vinklar , som därigenom bryter upp de återstående hörn av grafen. Liksom Xo-graferna innehåller grafen högst en kant per kon [1] (för den valda vertexen), men de skiljer sig åt i hur kanten väljs. Medan Yao-grafer väljer närmaste vertex enligt rymdmetriken bestämmer -grafen en fast stråle som finns i varje kon (vanligtvis används vinkelhalveringslinjen) och väljer närmaste granne enligt den ortogonala projektionen på den strålen. Den resulterande grafen visar några fina egenskaper för spännande diagram [2] . $\Theta$ $\Theta$ $\Theta$

$\Theta$ -grafer beskrevs först av Clarkson [3] 1987 och oberoende av Keil [4] 1988.

Byggnad

$\Theta$ -grafer ges av flera parametrar som bestämmer dess konstruktion. Den mest uppenbara parametern är , som motsvarar antalet identiska koner som bryter upp utrymmet runt varje vertex. I synnerhet för vertex kan konen av representeras som två oändliga strålar som utgår från denna punkt med en vinkel mellan dem. Med hänsyn till kan vi markera dessa koner som medurs. Dessa koner delar upp planet och delar också upp den återstående uppsättningen av hörn i grafen (förutsatt att hörnen är gemensamma ) i uppsättningar igen med avseende på punkten . Varje vertex i grafen har samma antal partitionskoner i samma orientering, och vi kan betrakta uppsättningen av hörn som faller inuti varje kon. $k$ $sid$ $sid$ $\theta =2\pi /k$ $sid$ $C_{1}\dots C_{k}$ $V_{1}\dots V_{k},$ $sid$

Betrakta en enda kon och vi måste specificera en annan stråle som kommer från , som vi kommer att beteckna . För varje vertex inuti konen , överväger vi den ortogonala projektionen av varje punkt på strålen . Låt vertexet ha den minsta projektionen, sedan läggs en kant till grafen . Detta är den största skillnaden från Yao-graferna, som alltid väljer den hörn som ligger närmast den . I exemplet i figuren skulle greve Yao inkludera kanten . $sid$ $l$ $V_i$ ${\displaystyle v\in V_{i))$ $l$ $r$ $\{p,r\}$ $sid$ ${\displaystyle \{p,q\))$

Konstruktionen av en -graf är möjlig med hjälp av en svepande linje i tiden [2] . $\Theta$ $O(n\log{n})$

Egenskaper

$\Theta$ -grafer visar några bra egenskaper för det geometriska spännträdet .

När parametern är en konstant är -grafen ett sparsamt spännträd. Varje kon ger högst en kant, de flesta hörn kommer att vara av låg grad, och hela grafen kommer att ha högst kanter. $k$ $\Theta$ $k\cdot n=O(n)$

Sträckfaktorn mellan två skelettpunkter definieras som förhållandet mellan det metriska avståndet och avståndet längs skelettet (det vill säga att följa skelettets kanter). Sträckfaktorn för hela skelettet är lika med den maximala stretchfaktorn för alla par av poäng. Som nämnts ovan,, då, om,-grafen har en sträckningsfaktor som inte överstiger [2] . Ombisektrisen väljs som en rät linje för den ortogonala projektionen i varje kon, såöverstiger inte sträckningskoefficienten [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 bildar en graf över närmaste grannar . Det är lätt att se att grafen hänger ihop, eftersom varje vertex är kopplat till något till vänster och något till höger, om de finns. För [6] [7] , [8] och [5] är det känt att -grafen är sammankopplad. Det finns opublicerade resultat som visar att -grafer också är kopplade för . Det finns många resultat som ger en övre och/eller nedre gräns på stretchfaktorn. $k=1$ $\Theta$ $k=2$ $k = 4$ $5$ $6$ $\geqslant 7$ $\Theta$ $\Theta$ $k = 3$

Om det är jämnt kan vi skapa en variant av -grafen känd som en semi -graf , där konerna delas upp i jämna och udda uppsättningar och endast kanter i jämna (eller bara udda) koner beaktas. Halvgrafer är kända för att ha några mycket intressanta egenskaper. Till exempel är det känt att en halvgraf (och därmed en -graf, som helt enkelt är föreningen av två komplementära halvgrafer) är 2-area [8] . $k$ ${\displaystyle \Theta _{k))$ ${\displaystyle \Theta _{k))$ ${\displaystyle \Theta _{k))$ $\Theta _{6}$ $\Theta _{6}$ $\Theta _{6}$

Theta graph ritprogram

Se även

Anteckningar

↑ En kon betyder i detta fall två strålar som utgår från en punkt, det vill säga en vinkel.
↑ 1 2 3 Narasimhan, Smid, 2007 .
↑ Clarkson, 1987 , sid. 56–65.
↑ Keil, 1988 , sid. 208–213.
↑ 1 2 Ruppert, Seidel, 1991 , sid. 207–210.
↑ Barba, Bose, De Carufel, van Renssen, Verdonschot, 2013 , sid. 109–120.
↑ Bose, Morin, van Renssen, Verdonschot, 2015 , sid. 108–119.
↑ 1 2 Bonichon, Gavoille, Hanusse, Ilcinkas, 2010 , sid. 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. Geometriska nyckelnätverk . - Cambridge University Press , 2007. - ISBN 0-521-81513-4 .
Clarkson K. Approximationsalgoritmer för planering av kortaste vägrörelse // In Proceedings of the nittonde årliga ACM-symposium on Theory of computing (STOC '87) / Alfred V. Aho (Ed.). — New York, NY, USA: ACM, 1987.
Ruppert J., Seidel R. Approximating av den d -dimensionella kompletta euklidiska grafen // In Proc. 3:e Kanada. Konf. Comput. Geom. — 1991.
Luis Barba, Prosenjit Bose, Jean-Lou De Carufel, André van Renssen, Sander Verdonschot. Om sträckfaktorn för theta-4-grafen // Algoritmer och datastrukturer. - Heidelberg: Springer, 2013. - S. 109–120. — (Föreläsningsanteckningar i datavetenskap). - doi : 10.1007/978-3-642-40104-6_10 .
Prosenjit Bose, Pat Morin, André van Renssen, Sander Verdonschot. θ 5 -grafen är en skiftnyckel // Computational Geometry. - 2015. - T. 48 , nr. 2 . — s. 108–119 . - doi : 10.1016/j.comgeo.2014.08.005 . - arXiv : 1212.0570 .
Bonichon N., Gavoille C., Hanusse N., Ilcinkas D. Samband mellan tetagrafer, Delaunay-triangulering och ortogonala ytor. // I grafteoretiska begrepp i datavetenskap. — Berlin/Heidelberg: Springer, 2010. — s. 266–278.