세타 그래프

계산 기하학에서, 테타 그래프 또는 $\theta {\displaystyle \mathrm{}}$ ${\displaystyle \Teta }$ -그래프는 야오 그래프와 유사한 기하학적 스패너의 일종이다.기본 구성 방법은 각 꼭지점 주위의 공간을 원뿔 집합으로 분할하는 것을 포함하며, 원뿔 집합은 그래프의 나머지 정점을 분할한다.$Yao{\displaystyle \mathrm{}}$ Graphs와 마찬가지로$display$ {\displaystyle $\Teta }$ -그래프는$$ 원뿔당 하나의 가장자리를 포함하며, 여기서 차이가 나는 것은 해당 가장자리를 선택하는 방법이다.Yao Graphs는 그래프의 미터 공간에 따라 가장 가까운 정점을 선택하지만, $Ⅱ{\displaystyle \mathrm{}}$ ${\displaystyle \Theta }$그래프는$$ 각 원뿔 안에 포함된 고정 광선(컨벤션적으로 원뿔의 이등분자)을 정의하고 그 광선에 직교 투영과 관련하여 가장 가까운 이웃을 선택한다.결과 그래프는 몇 가지 좋은 스패너 특성을 보여준다.^[1]

${\displaystyle \mathrm{\theta }}$ ${\displaystyle \Theta}$ -그래프는$$ 클락슨이^[2] 1987년에 처음, 케이일이^[3] 1988년에 독자적으로 기술했다.

건설

${\displaystyle \mathrm{\theta }}$ ${\displaystyle \Theta }$ -그래프는$$ 구성을 결정하는 몇 가지 매개 변수를 사용하여 지정된다.가장 분명한 매개변수는 $k{\displaystyle }$ ${\displaystyle k}$이며$,$ 이는 각 꼭지점 주위의 공간을 분할하는 등각 원뿔의 수에 해당한다.특히 꼭지점 $p{\displaystyle }$ ${\displaystyle p}$의 경우$,$ $p{\displaystyle }$ ${\displaystyle p}$에 대한 원뿔이 그 사이에서$$ $각도{\displaystyle }$ ${\displaystyle =}$ = ${\displaystyle 2}$ ${\displaystyle /}$ / ${\displaystyle k}${\$displaystyle \theta$= $2\pi /k}$을(를) 가진 두 개의 무한 광선이 방출되는 것으로 상상할 수 있다$$.$p{\displaystyle }$ ${\displaystyle p}$에 관하여$,$ 우리는$$ 이 콘을 $C{\displaystyle {}_{}}$ $1{\displaystyle {}_{}}$ {\displaystyle $C_{$1}에서$$ ${\displaystyle C_{}}$ $k{\displaystyle {}_{}}$ ${\$ C_${k$$}$까지로 라벨을 붙일 수 있는데$,$ 이 라벨은 통상적으로 C ${\displaystyle {1\mathrm{}}_{}}$ ${\$}에서 평면과 관련하여 0이 되도록 개방된다.이러한 원뿔이 평면을 분할할 때, 그들은 또한 그래프의 나머지 정점 집합(일반 위치를 가정)을 V 1 ${\$1}를 $통해$ $세트{\displaystyle {}_{}}$ V ${\displaystyle 1_{}}$ ${\$로 분할한다$.$ $다시{\displaystyle }$ p$${\$displaystystyle p}$에 관하여 그래프에 있는 모든 정점들은 동일한 수의 원뿔을 동일한 방향으로 얻는다.이온, 그리고 우리는 각각에 들어가는 정점의 집합을 고려할 수 있다.

단일 원뿔을 고려하여 $p{\displaystyle }$ ${\$$displaystyle$ $l$$}$에서 $나오는$ 다른 광선을 지정해야 하며$,$ 이 $광선$은 l ${\displaystyle$ l}에 레이블을 붙일 것이다$.$ V $i{\displaystyle {}_{}}$ ${\$의 모든 정점에 대해$,$ 각$$V${\displaystyle i_{}}$ V i ${\displaystystyle v_$$\{$$i$$}$에 직교 투영하는 것을 고려한다.${\displaystyle r}$ ${\displaystyle r}$은(는) 이러한 투영에 가장 가까운 정점이며, 그런 다음 에지${\displaystyle }${${\displaystyle p}$ ${\displaystyle ,}$ ${\displaystyle r}$ ${\displaystyle \}}$ ${\displaystyle \{p,r\}}$가 그래프에 추가된다$$.이는 항상 가장 가까운 정점을 선택하는 야오 그래프와의 주요 차이점이다. 예시 이미지에서 야오 그래프는 가장자리${\displaystyle }${${\displaystyle p}$ ,${\displaystyle q}$ ${\displaystyle \}}$ ${\displaystyle$\{$p,q\}$을 대신$$ 포함한다.

$\theta {\displaystyle \mathrm{}}$ ${\displaystyle \Theta}$ -그래프는$$ $O{\displaystyle }$(${\displaystyle n}$ ${\displaystyle \log logn}$ )${\displaystyle O(n\log {n})$ 시간$$ 내에 sweeepline 알고리즘을 사용하여 구성할 수 있다.^[1]

특성.

${\displaystyle \mathrm{\theta }}$ ${\displaystyle \Theta}$ -그래프는$$ 몇 가지 양호한 기하학적 스패너 특성을 나타낸다.

매개 변수 $k{\displaystyle }$ ${\displaystyle k}$이(가) 상수인 경우 $\theta {\displaystyle \mathrm{}}$ ${\displaystyle \Teta }$ -그래프는$$ 희소 스패너입니다.각 원뿔이 원뿔당 최대 하나의 가장자리를 생성하므로 대부분의 정점들은 작은 정도를 가지며, 전체 그래프는 최대 $k{\displaystyle }$ ${\displaystyle \cdot n}$= ${\displaystyle O}$(${\displaystyle n}$ ${\displaystyle )}$ ${\displaystyle k\cdot n=O(n)}$개의$$ 가장자리를 가질 것이다.

스패너에서 점 쌍 사이의 스트레치 계수는 측정 기준 공간 거리와 스패너 내 거리 사이의 비율로 정의된다(즉, 스패너의 다음 가장자리로부터의 거리).전체 스패너의 스트레치 계수는 스패너 내의 모든 포인트 쌍에 대한 최대 스트레치 계수다.Recall from above that ${\displaystyle \theta =2\pi /k}$, then when ${\displaystyle k\geq 9}$, the ${\displaystyle \Theta }$-graph has a stretch factor of at most ${\displaystyle 1/(\cos \theta -\sin \theta )}$.^[1] If the orthogonal projection line ${\displaystyle l}$각 원뿔에서 이등분자가 ${\displaystyle \mathrm{되도록}}$ 선택한 다음, $k{\displaystyle }$ ${\displaystyle \ge }$ 7 ${\displaystyle k\geq$ 7$\}$의 경우 신장비는 최대 1${\displaystyle }$/(${\displaystyle 1}$-${\displaystyle 2}$ sin ${\displaystyle \sin }$ ( ${\displaystyle }$/ ${\displaystyle k}$)${\displaystyle }${\$displaystyle$ 1$/(1-2\sin(\pi /k$^[4]

$k{\displaystyle }$= ${\displaystyle 1}$ ${\displaystyle k=1}$의 경우$$$graph{\displaystyle \mathrm{}}$ ${\displaystyle \Teta }$ - 그래프가$$ 가장 가까운 인접 그래프를 형성한다.$k{\displaystyle }$= ${\displaystyle 2}$ ${\displaystyle k=2}$의 경우$,$ 각 꼭지점이 왼쪽의 어떤 것에 연결되고, 어떤 것이 존재한다면 오른쪽의 어떤 것에 연결되므로 그래프가 연결된 것을 쉽게 알 수 있다.$k{\displaystyle }$= ${\displaystyle 3}$ ${\displaystyle k=3$^[5] $4{\displaystyle \mathrm{}}$ ${\displaystyle$ $4$$}$ $5$^[6] ${\displaystyle$ $5},$^[7] 6 ${\displaystyle$ $\geq$ 7$},$^{[8] [4]}$for{\displaystyle \mathrm{}}$ 7 ${\$$displaystystyle \theta}$ -그래프가$$ 연결된 것으로 알려져 있다.또한 이러한 결과 중 다수는 스패닝 비율에 상한 및 하한을 부여한다.

$k{\displaystyle }$ ${\displaystyle k}$이(가) 짝수일 때, 우리는 ${\displaystyle {\mathrm{}}_{}}$ ${\displaystyle k_{}}$ ${\$그래프로 알려진 θ k ${\$그래프의 변형을 만들 수 있는데, 여기서 원뿔 자체는 짝수 및 홀수 세트로 분할되고 가장자리만 고려된다.이상한 속임수를 쓰다반- ${\displaystyle {\mathrm{}}_{}}$ ${\displaystyle k_{}}$ ${\$ -그래프는$$ 그들 자신의 아주 좋은 성질을 가지고 있는 것으로 알려져 있다.예를 들어, 반 ${\displaystyle {\mathrm{}}_{}}$ ${\displaystyle {6\mathrm{}}_{}}$ ${\$ $_{$$6}$ -그래프$$(결과적으로 ${\displaystyle {\theta \mathrm{}}_{}}$ 6 ${\$ -그래프$$$$)는 2-spanner인 것으로 알려져 있다.^[8]

Theta 그래프 그리기 소프트웨어

• Java로 작성된 도구
• CGAL(Computing Geometric Algorithm Library)의 콘 기반 스패너

참고 항목

• 야오 그래프
• 반야오 그래프
• 기하 스패너

참조