text: Theta graphs are important geometric graphs that have many applications, including wireless networking, motion planning, real-time animation, and minimum-spanning tree construction. We give closed form expressions for the average degree of theta graphs of a homogeneous Poisson point process over the plane. We then show that essentially the same bounds---with vanishing error terms---hold for theta graphs of finite sets of points that are uniformly distributed in a square. Finally, we show that the number of edges in a theta graph of points uniformly distributed in a square is concentrated around its expected value.
  @cite_5: A Directional Nearest-Neighbor graph is defined on a finite set of points in the plane by drawing an arc from each point X to its nearest neighbor in each of r divisions of the plane relative to X. We prove that Directional Nearest-Neighbor graphs having @math are strongly connected.
  @cite_15: Abstract We consider n independent points with a common but arbitrary density f in R d . Two points ( X i , X j ) are joined by an edge when a certain set S ( X i , X j ) does not contain any other data points. The expected number E ( N ) of edges in the graph depends upon n , f and the definition of S . Examples include rectangle, spheres and loons; these lead to the graph of all dominance pairs, the Gabriel graph and the relative neighborhood graph, respectively. Other graphs covered by our analysis include the nearest neighbor graph and the directional nearest neighbor graph. In all cases, we obtain asymptotic lower bounds that do not depend upon f (and are hence useful in all applications involving these graphs, since we usually do not know f ). For sparse graphs, exact asymptotic constants are obtained for E ( N ) that are valid for all densities.
  @cite_11: The problem of finding a minimum spanning tree connecting n points in a k-dimensional space is discussed under three common distance metrics -- Euclidean, rectilinear, and @math . By employing a subroutine that solves the post office problem, we show that, for fixed k @math 3, such a minimum spanning tree can be found in time O( @math ), where a(k) = @math . The bound can be improved to O( @math ) for points in the 3-dimensional Euclidean space. We also obtain o( @math ) algorithms for finding a farthest pair in a set of n points and for other related problems.
summary: In contrast, properties of other proximity graphs of random point sets have been studied extensively: Devroye @cite_15 presents a general theorem for obtaining exact leading constants for the expected degree of a number of proximity graphs over point sets drawn from a large class of distributions. This theorem can be applied to Gabriel graphs, relative neighbourhood graphs, and nearest-neighbour graphs. This work [Section 7] devroye:expected also mentions directional nearest-neighbour graphs,'' now commonly known as Yao graphs @cite_5 @cite_11 , and points out that the general theorem does not apply to these (nor does it apply to theta graphs---for the same reasons).