Type of geometric spanner graph
In computational geometry, the Theta graph, or formula_1-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 formula_1-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 formula_1-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.
formula_1-graphs were first described by Clarkson in 1987 and independently by Keil in 1988.
Construction.
formula_1-graphs are specified with a few parameters which determine their construction. The most obvious parameter is formula_6, which corresponds to the number of equal angle cones that partition the space around each vertex. In particular, for a vertex formula_7, a cone about formula_7 can be imagined as two infinite rays emanating from it with angle formula_9 between them. With respect to formula_7, we can label these cones as formula_11 through formula_12 in a counterclockwise pattern from formula_11, 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 formula_14 through formula_15, again with respect to formula_7. 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 formula_7, which we will label formula_18. For every vertex in formula_19, we consider the orthogonal projection of each formula_20 onto formula_18. Suppose that formula_22 is the vertex with the closest such projection, then the edge formula_23 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 formula_24 instead.
Construction of a formula_1-graph is possible with a sweepline algorithm in formula_26 time.
Properties.
formula_1-graphs exhibit several good geometric spanner properties.
When the parameter formula_6 is a constant, the formula_1-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 formula_30 edges.
The stretch factor between any pair of points in a spanner is defined as the ratio between their metric space distance, and their distance within the spanner (i.e. from following edges of the spanner). The stretch factor of the entire spanner is the maximum stretch factor over all pairs of points within it. Recall from above that formula_9, then when formula_32, the formula_1-graph has a stretch factor of at most formula_34. If the orthogonal projection line formula_18 in each cone is chosen to be the bisector, then for formula_36, the spanning ratio is at most formula_37.
For formula_38, the formula_1-graph forms a nearest neighbor graph. For formula_40, it is easy to see that the graph is connected, as each vertex will connect to something to its left, and something to its right, if they exist. For formula_41,formula_42 formula_43, formula_44, and formula_45, the formula_1-graph is known to be connected. Many of these results also give upper and/or lower bounds on their spanning ratios.
When formula_6 is an even number, we can create a variant of the formula_48-graph known as the "half-formula_48-graph", where the cones themselves are partitioned into "even" and "odd" sets in an alternating fashion, and edges are only considered in the even cones (or, only the odd cones). Half-formula_48-graphs are known to have some very nice properties of their own. For example, the half-formula_51-graph (and, consequently, the formula_51-graph, which is just the union of two complementary half-formula_51-graphs) is known to be a 2-spanner.
References.
 ;templatestyles src="Reflist/styles.css" / ;