Theta -graf - Theta graph

I beräkningsgeometri är Theta -grafen eller -grafen en typ av geometrisk nyckel som liknar en Yao -graf . Den grundläggande konstruktionsmetoden innebär att utrymmet runt varje hörn delas upp i en uppsättning kottar , som själva delar upp grafens återstående hörn. Liksom Yao Graphs innehåller en -graf högst en kant per kon; där de skiljer sig är hur den kanten väljs. Medan Yao Graphs kommer att välja det närmaste hörnet enligt grafens metriska utrymme , definierar -grafen en fixerad stråle som finns i varje kon (vanligtvis konens bisektor) och väljer den närmaste grannen med avseende på ortogonala projektioner till den strålen. Den resulterande grafen uppvisar flera bra nyckelegenskaper. ${\ displaystyle \ Theta}$${\ displaystyle \ Theta}$${\ displaystyle \ Theta}$

${\ displaystyle \ Theta}$-grafer beskrevs först av Clarkson 1987 och oberoende av Keil 1988.

Konstruktion

Exempelkon av en -graf som kommer från med ortogonal projektionslinje${\ displaystyle \ Theta}$${\ displaystyle p}$${\ displaystyle l}$

${\ displaystyle \ Theta}$-grafer specificeras med några parametrar som bestämmer deras konstruktion. Den mest uppenbara parametern är , vilket motsvarar antalet lika vinkelkottar som delar utrymmet runt varje hörn. I synnerhet för en toppunkt kan en kon om föreställas som två oändliga strålar som utgår från den med vinkel mellan dem. Med avseende på , kan vi märka dessa kottar som genom i ett moturs mönster från , som konventionellt öppnas så att dess sektorer har vinkel 0 i förhållande till planet. När dessa kottar delar planet, delar de också upp den återstående toppunktsuppsättningen i grafen (antar allmän position ) i uppsättningarna genom , igen med avseende på . Varje toppunkt i grafen får samma antal koner i samma orientering, och vi kan överväga uppsättningen hörn som faller in i varje. ${\ displaystyle k}$${\ displaystyle p}$${\ displaystyle p}$${\ displaystyle \ theta = 2 \ pi /k}$${\ displaystyle p}$${\ displaystyle C_ {1}}$${\ displaystyle C_ {k}}$${\ displaystyle C_ {1}}$${\ displaystyle V_ {1}}$${\ displaystyle V_ {k}}$${\ displaystyle p}$

Med tanke på en enda kon måste vi ange en annan stråle som kommer från , som vi kommer att märka . För varje hörn i , betraktar vi den ortogonala projektionen av varje på . Antag att det är toppunktet med den närmaste dylika projektionen, då läggs kanten till diagrammet. Detta är den primära skillnaden från Yao Graphs som alltid väljer närmaste hörn; i exempelbilden skulle en Yao -graf inkludera kanten istället. ${\ displaystyle p}$${\ displaystyle l}$${\ displaystyle V_ {i}}$${\ displaystyle v \ i V_ {i}}$${\ displaystyle l}$${\ displaystyle r}$${\ displaystyle \ {p, r \}}$${\ displaystyle \ {p, q \}}$

Konstruktion av en -graf är möjlig med en svepalgoritm i tid. ${\ displaystyle \ Theta}$${\ displaystyle O (n \ log {n})}$

Egenskaper

${\ displaystyle \ Theta}$-grafer uppvisar flera bra geometriska nyckelegenskaper .

När parametern är en konstant är -grafen en gles nyckel. Eftersom varje kon genererar högst en kant per kon kommer de flesta hörnen att ha liten grad, och den övergripande grafen kommer att ha högst kanter. ${\ displaystyle k}$${\ displaystyle \ Theta}$${\ displaystyle k \ cdot n = O (n)}$

Den brottöjning mellan varje par av punkter i en skruvnyckel är definierad som förhållandet mellan deras metriskt rum avstånd, och deras avstånd i skruvnyckel (dvs från följande kanterna på skruvnyckel). Sträckningsfaktorn för hela skiftnyckeln är den maximala sträckningsfaktorn över alla punkter i den. Minns från ovan att , sedan när den har -graph en sträckfaktor av högst . Om den ortogonala projektionslinjen i varje kon väljs för att vara bisektorn, då är spänningsförhållandet högst . ${\ displaystyle \ theta = 2 \ pi /k}$${\ displaystyle k \ geq 9}$${\ displaystyle \ Theta}$${\ displaystyle 1/(\ cos \ theta -\ sin \ theta)}$${\ displaystyle l}$${\ displaystyle k \ geq 7}$${\ displaystyle 1 /(1-2 \ sin (\ pi /k))}$

För den bildar -graph en närmaste granne graf . För det är lätt att se att grafen är ansluten, eftersom varje toppunkt kommer att ansluta till något till vänster och något till höger om de finns. För , , och den -graph är känd för att vara ansluten. Många av dessa resultat ger också övre och/eller nedre gränser för deras spänningsförhållanden. ${\ displaystyle k = 1}$${\ displaystyle \ Theta}$${\ displaystyle k = 2}$${\ displaystyle k = 3}$${\ displaystyle 4}$ ${\ displaystyle 5}$${\ displaystyle 6}$${\ displaystyle \ geq 7}$${\ displaystyle \ Theta}$

När är ett jämnt tal kan vi skapa en variant av -grafen som kallas halvgrafen , där kottarna själva delas upp i jämna och udda uppsättningar på ett växlande sätt, och kanterna betraktas endast i de jämna konerna (eller , bara de udda kottarna). Halvgrafer är kända för att ha några mycket fina egenskaper. Till exempel är halvgrafen (och följaktligen -grafen, som bara är sammanslutningen av två kompletterande halvgrafer) kända för att vara en 2 -skiftnyckel. ${\ displaystyle k}$${\ displaystyle \ Theta _ {k}}$${\ displaystyle \ Theta _ {k}}$${\ displaystyle \ Theta _ {k}}$${\ displaystyle \ Theta _ {6}}$${\ displaystyle \ Theta _ {6}}$${\ displaystyle \ Theta _ {6}}$

Programvara för att rita Theta -grafer

• Ett verktyg skrivet i Java
• Konbaserade nycklar i Computational Geometry Algorithms Library (CGAL)

Se även

• Yao -graf
• Semi-Yao graf
• geometrisk skiftnyckel

Referenser