The Price of Order
We present tight bounds on the spanning ratio of a large family of ordered θ-graphs. A θ-graph partitions the plane around each vertex into m disjoint cones, each having aperture θ = 2π/m. An ordered θ-graph is constructed by inserting the vertices one by one and connecting each vertex to the closest previously-inserted vertex in each cone. We show that for any integer k ≥ 1, ordered θ-graphs with 4k + 4 cones have a tight spanning ratio of 1 + 2sin(θ/2)/(cos(θ/2) -sin(θ/2)). We also show that for any integer k ≥ 2, ordered θ-graphs with 4k + 2 cones have a tight spanning ratio of 1/(1 - 2sin(θ/2)). We provide lower bounds for ordered θ-graphs with 4k + 3 and 4k + 5 cones. For ordered θ-graphs with 4k + 2 and 4k + 5 cones these lower bounds are strictly greater than the worst case spanning ratios of their unordered counterparts. These are the first results showing that ordered θ-graphs have worse spanning ratios than unordered θ-graphs. Finally, we show that, unlike their unordered counterparts, the ordered θ-graphs with 4, 5, and 6 cones are not spanners.
|Keywords||geometric graphs, Spanners, spanning ratio, stretch factor, tight bounds|
|Journal||International Journal of Computational Geometry and Applications|
Bose, P, Morin, P, & Van Renssen, A. (André). (2016). The Price of Order. International Journal of Computational Geometry and Applications, 26(3-4), 135–149. doi:10.1142/S0218195916600013