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_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.
  @cite_17: Motivated by applications of Gabriel graphs and Yao graphs in wireless ad-hoc networks, we show that the maximum degree of a random Gabriel graph or Yao graph defined on n points drawn uniformly at random from a unit square grows as ?(log n log log n) in probability.
summary: As discussed in the introduction, a plethora of literature exists on theta graphs and their applications, though most of this work focuses on worst-case analysis. One notable exception is the work of Devroye al @cite_17 who study the maximum degree of theta graphs and show that, if @math is a set of @math points independently and uniformly distributed in a certain unit square, then @math has maximum degree concentrated around @math . Devroye al actually consider the closely-related Yao graphs @cite_5 @cite_11 , but their proofs apply, almost without modification, to theta graphs.