Theta graf - Theta graph

v výpočetní geometrie, Theta grafnebo ${ displaystyle Theta}$-graf, je typ geometrický klíč podobný a Yao graf. Základní metoda konstrukce zahrnuje rozdělení prostoru kolem každého vrcholu do sady šišky, které samy rozdělují zbývající vrcholy grafu. Stejně jako Yao Graphs, a ${ displaystyle Theta}$-graf obsahuje nejvýše jednu hranu na kužel; kde se liší, je způsob výběru této hrany. Zatímco Yao Graphs vybere nejbližší vrchol podle metrický prostor grafu, ${ displaystyle Theta}$-graph definuje stálý paprsek obsažený v každém kuželu (obvykle půlící část kužele) a vybere nejbližšího souseda vzhledem k ortogonálním projekcím k tomuto paprsku. Výsledný graf vykazuje několik dobrých vlastností klíče.^[1]

${ displaystyle Theta}$-grafy byly poprvé popsány Clarksonem^[2] v roce 1987 a nezávisle Keil^[3] v roce 1988.

Konstrukce

Příklad kuželu a ${ displaystyle Theta}$-graf vycházející z ${ displaystyle p}$ s ortogonální projekční čarou ${ displaystyle l}$

${ displaystyle Theta}$- grafy jsou specifikovány s několika parametry, které určují jejich konstrukci. Nejviditelnějším parametrem je ${ displaystyle k}$, což odpovídá počtu kuželů se stejným úhlem, které rozdělují prostor kolem každého vrcholu. Zejména pro vrchol ${ displaystyle p}$, kužel o ${ displaystyle p}$ lze představit jako dva nekonečné paprsky vycházející z něj pod úhlem ${ displaystyle theta = 2 pi / k}$ mezi nimi. S ohledem na ${ displaystyle p}$, můžeme tyto šišky označit jako ${ displaystyle C_ {1}}$ přes ${ displaystyle C_ {k}}$ proti směru hodinových ručiček od ${ displaystyle C_ {1}}$, který se konvenčně otevírá tak, že jeho přímka má úhel 0 vzhledem k rovině. Protože tyto kužele rozdělují rovinu, rozdělují také zbývající vrcholovou množinu grafu (za předpokladu obecná pozice ) do sad ${ displaystyle V_ {1}}$ přes ${ displaystyle V_ {k}}$, opět s ohledem na ${ displaystyle p}$. Každý vrchol v grafu získá stejný počet kuželů ve stejné orientaci a můžeme uvažovat o sadě vrcholů, které spadají do každého.

Vzhledem k jedinému kuželu musíme určit další paprsek vycházející z ${ displaystyle p}$, které označíme ${ displaystyle l}$. Pro každý vrchol v ${ displaystyle V_ {i}}$, uvažujeme ortogonální projekci každého z nich ${ displaystyle v ve V_ {i}}$ na ${ displaystyle l}$. Předpokládejme to ${ displaystyle r}$ je vrchol s nejbližší takovou projekcí, pak hrana ${ displaystyle {p, r }}$ je přidán do grafu. Toto je primární rozdíl od Yao Graphs, které vždy vybírají nejbližší vrchol; v ukázkovém obrázku by Yao Graph zahrnoval okraj ${ displaystyle {p, q }}$ namísto.

Stavba a ${ displaystyle Theta}$-graf je možný s a algoritmus sweepline v ${ displaystyle O (n log {n})}$ čas.^[1]

Vlastnosti

${ displaystyle Theta}$-grafy vykazují několik dobrých geometrický klíč vlastnosti.

Když parametr ${ displaystyle k}$ je konstanta, ${ displaystyle Theta}$-graph je řídký klíč. Protože každý kužel generuje nejvýše jednu hranu na kužel, bude mít většina vrcholů malý stupeň a celkový graf bude mít nejvýše ${ displaystyle k cdot n = O (n)}$ hrany.

The napínací faktor mezi jakoukoli dvojicí bodů v klíči je definován jako poměr mezi jejich vzdáleností v metrickém prostoru a jejich vzdáleností v klíči (tj. od následujících hran klíče). Faktor roztažení celého klíče je maximální faktor roztažení ve všech dvojicích bodů v něm. Připomeňme si to výše ${ displaystyle theta = 2 pi / k}$, pak kdy ${ displaystyle k geq 9}$, ${ displaystyle Theta}$-graph má napínací faktor maximálně ${ displaystyle 1 / ( cos theta - sin theta)}$.^[1] Pokud je ortogonální projekční čára ${ displaystyle l}$ v každém kuželu je vybrána půlení, pak pro ${ displaystyle k geq 7}$, rozpětí je maximálně ${ Displaystyle 1 / (1-2 sin ( pi / k))}$.^[4]

Pro ${ displaystyle k = 1}$, ${ displaystyle Theta}$-graf tvoří a graf nejbližšího souseda. Pro ${ displaystyle k = 2}$, je snadné vidět, že graf je spojen, protože každý vrchol se připojí k něčemu nalevo a něco napravo, pokud existují. Pro ${ displaystyle k = 3}$^[5],${ displaystyle 4}$^[6] ${ displaystyle 5}$,^[7] ${ displaystyle 6}$,^[8] a ${ displaystyle geq 7}$,^[4] the ${ displaystyle Theta}$-graph je známo, že je připojen. Mnoho z těchto výsledků také dává horní a / nebo dolní mez jejich rozpětí.

Když ${ displaystyle k}$ je sudé číslo, můžeme vytvořit variantu ${ displaystyle Theta _ {k}}$-graf známý jako polovina-${ displaystyle Theta _ {k}}$-graf, kde jsou rozděleny samotné kužely dokonce a zvláštní sady střídavě, a hrany jsou považovány pouze u sudých kuželů (nebo pouze u lichých kuželů). Polovina-${ displaystyle Theta _ {k}}$- je známo, že grafy mají některé velmi pěkné vlastnosti. Například poloviční${ displaystyle Theta _ {6}}$-graf (a následně ${ displaystyle Theta _ {6}}$-graf, který je jen spojením dvou komplementárních polovin${ displaystyle Theta _ {6}}$-graphs) je známo, že je 2-klíčový.^[8]

Software pro kreslení grafů Theta

• Nástroj napsaný v Javě
• Kónické klíče v knihovně algoritmů výpočetní geometrie (CGAL)

Viz také

• Yao graf
• Semi-Yao graf
• geometrický klíč

Reference