In computational geometry, the Theta graph, or -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-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-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.

-graphs were first described by Clarkson in 1987 and independently by Keil in 1988.

Construction

, 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. 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.

instead.

-graph is possible with a sweepline algorithm time.

Properties

-graphs exhibit several useful geometric spanner properties.

edges.

The stretch factor..

-graph forms a nearest neighbor graph,,,-graph is known to be connected. Many of these results also give upper and/or lower bounds on their spanning ratios.

is an even number-graph known as the -graph, where the cones themselves are partitioned into even and odd-graphs) is known to be a 2-spanner.

Software for drawing Theta graphs

• A tool written in Java

• Cone-based Spanners in Computational Geometry Algorithms Library (CGAL)

See also

• Yao graph

• Semi-Yao graph

• geometric spanner

References