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. Length, formatting, and copyright restrictions make this paper more difficult to read than necessary.

Additional Metadata
Conference 11th Workshop on Analytic Algorithmics and Combinatorics, ANALCO 2014
Citation
Morin, P, & Verdonschot, S. (Sander). (2014). On the average number of edges in theta graphs. Presented at the 11th Workshop on Analytic Algorithmics and Combinatorics, ANALCO 2014.