Theta graph

In computational geometry, the Theta graph, or Θ {displaystyle Theta } -graph, is a type of geometric spanner similar to a Yao graph. The basic method of construction involves partitioning the space around each vertex into a set of cones, which themselves partition the remaining vertices of the graph. Like Yao Graphs, a Θ {displaystyle Theta } -graph contains at most one edge per cone; where they differ is how that edge is selected. Whereas Yao Graphs will select the nearest vertex according to the metric space of the graph, the Θ {displaystyle Theta } -graph defines a fixed ray contained within each cone (conventionally the bisector of the cone) and selects the nearest neighbor with respect to orthogonal projections to that ray. The resulting graph exhibits several good spanner properties. Θ {displaystyle Theta } -graphs were first described by Clarkson in 1987 and independently by Keil in 1988. Θ {displaystyle Theta } -graphs are specified with a few parameters which determine their construction. The most obvious parameter is k {displaystyle k} , which corresponds to the number of equal angle cones that partition the space around each vertex. In particular, for a vertex p {displaystyle p} , a cone about p {displaystyle p} can be imagined as two infinite rays emanating from it with angle θ = 2 π / k {displaystyle heta =2pi /k} between them. With respect to p {displaystyle p} , we can label these cones as C 1 {displaystyle C_{1}} through C k {displaystyle C_{k}} in a counterclockwise pattern from C 1 {displaystyle C_{1}} , which conventionally opens so that its bisector has angle 0 with respect to the plane. As these cones partition the plane, they also partition the remaining vertex set of the graph (assuming general position) into the sets V 1 {displaystyle V_{1}} through V k {displaystyle V_{k}} , again with respect to p {displaystyle p} . Every vertex in the graph gets the same number of cones in the same orientation, and we can consider the set of vertices that fall into each. Considering a single cone, we need to specify another ray emanating from p {displaystyle p} , which we will label l {displaystyle l} . For every vertex in V i {displaystyle V_{i}} , we consider the orthogonal projection of each v ∈ V i {displaystyle vin V_{i}} onto l {displaystyle l} . Suppose that r {displaystyle r} is the vertex with the closest such projection, then the edge { p , r } {displaystyle {p,r}} is added to the graph. This is the primary difference from Yao Graphs which always select the nearest vertex; in the example image, a Yao Graph would include the edge { p , q } {displaystyle {p,q}} instead. Construction of a Θ {displaystyle Theta } -graph is possible with a sweepline algorithm in O ( n log ⁡ n ) {displaystyle O(nlog {n})} time. Θ {displaystyle Theta } -graphs exhibit several good geometric spanner properties. When the parameter k {displaystyle k} is a constant, the Θ {displaystyle Theta } -graph is a sparse spanner. As each cone generates at most one edge per cone, most vertices will have small degree, and the overall graph will have at most k ⋅ n = O ( n ) {displaystyle kcdot n=O(n)} edges.