Theta graph

This article is about geometric graphs defined from nearest neighbors in wedges. For theta graphs in graph theory (three paths with shared endpoints), see Glossary of graph theory.

In computational geometry, the Theta graph, or \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 \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 \Theta-graph defines a fixed ray contained within each cone (conventionally the bisector of the cone) and selects the nearest neighbour with respect to orthogonal projections to that ray. The resulting graph exhibits several good spanner properties .[1]

\Theta-graphs were first described by Clarkson[2] in 1987 and independently by Keil[3] in 1988.

Construction

Example cone of a \Theta-graph emanating from p with orthogonal projection line l

\Theta-graphs are specified with a few parameters which determine their construction. The most obvious parameter is k, which corresponds to the number of equal angle cones that partition the space around each vertex. In particular, for a vertex p, a cone about p can be imagined as two infinite rays emanating from it with angle \theta = 2\pi/k between them. With respect to p, we can label these cones as C_1 through C_k in an anti-clockwise pattern from 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 through V_k, again with respect to 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, which we will label l. For every vertex in V_i, we consider the orthogonal projection of each v \in V_i onto l. Suppose that r is the vertex with the closest such projection, then the edge \{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\} instead.

Construction of a \Theta-graph is possible with a sweepline algorithm in O(n \log{n}) time.[1]

Properties

\Theta-graphs exhibit several good geometric spanner properties.

When the parameter k is a constant, the \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 \cdot n = O(n) 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 \theta = 2\pi/k, then when k \geq 9, the \Theta-graph has a stretch factor of at most 1/(\cos\theta - \sin\theta).[1] If the orthogonal projection line l in each cone is chosen to be the bisector, then for k \geq 7, the spanning ratio is at most 1/(1 - 2\sin(\pi / k)).[4]

For k = 1, the \Theta-graph forms a nearest neighbour graph. For k = 2, 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 k = 4,[5] 5,[6] 6,[7] and \geq 7,[4] the \Theta-graph is known to be connected. As yet unpublished results indicate that \Theta-graphs are connected for k = 3, as well. Many of these results also give upper and/or lower bounds on their spanning ratios.

When k is an even number, we can create a variant of the \Theta_k-graph known as the half-\Theta_k-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-\Theta_k-graphs are known to have some very nice properties of their own. For example, the half-\Theta_6-graph (and, consequently, the \Theta_6-graph, which is just the union of two complimentary half-\Theta_6-graphs) is known to be a 2-spanner.[7]

See also

References

  1. ↑ 1.0 1.1 1.2 Narasimhan, Giri; Smid, Michiel (2007), Geometric Spanner Networks, Cambridge University Press, ISBN 0-521-81513-4.
  2. ↑ K. Clarkson. 1987. Approximation algorithms for shortest path motion planning. In Proceedings of the nineteenth annual ACM symposium on Theory of computing (STOC '87), Alfred V. Aho (Ed.). ACM, New York, NY, USA, 56–65.
  3. ↑ Keil, J. (1988). Approximating the complete Euclidean graph. SWAT 88, 208–213.
  4. ↑ 4.0 4.1 Ruppert, J., & Seidel, R. (1991). Approximating the d-dimensional complete Euclidean graph. In Proc. 3rd Canad. Conf. Comput. Geom (pp. 207–210).
  5. ↑ Barba, Luis; Bose, Prosenjit; De Carufel, Jean-Lou; van Renssen, André; Verdonschot, Sander (2013), "On the stretch factor of the theta-4 graph", Algorithms and data structures, Lecture Notes in Computer Science 8037, Heidelberg: Springer, pp. 109–120, arXiv:1303.5473, doi:10.1007/978-3-642-40104-6_10, MR 3126350.
  6. ↑ Bose, Prosenjit; Morin, Pat; van Renssen, André; Verdonschot, Sander (2015), "The θ5-graph is a spanner", Computational Geometry 48 (2): 108–119, arXiv:1212.0570, doi:10.1016/j.comgeo.2014.08.005, MR 3260251.
  7. ↑ 7.0 7.1 Bonichon, N., Gavoille, C., Hanusse, N., & Ilcinkas, D. (2010). Connections between theta-graphs, Delaunay triangulations, and orthogonal surfaces. In Graph Theoretic Concepts in Computer Science (pp. 266–278). Springer Berlin/Heidelberg.