On the average number of edges in theta graphs
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.
|Conference||11th Workshop on Analytic Algorithmics and Combinatorics, ANALCO 2014|
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.