Abstract
Motivated by the problem of orienting directional antennas in wireless communication networks, we study average bounded-angle minimum spanning trees. Let P be a set of points in the plane and let α be an angle. An α-spanning tree (α-ST) of P is a spanning tree of the complete Euclidean graph induced by P with the restriction that all edges incident to each point p ∈ P lie in a wedge of angle α with apex p. An α-minimum spanning tree (α-MST) of P is an α-ST with minimum total edge length. An average-α-spanning tree (denoted by α-ST) is a spanning tree with the relaxed condition that incident edges to all points lie in wedges with average angle α. An average-α-minimum spanning tree (α-MST) is an α-ST with minimum total edge length. In this paper, we focus on α = 2π/3. Let A (2π/3) be the smallest ratio of the length of the 2π/3-MST to the length of the standard MST, over all sets of points in the plane. Biniaz, Bose, Lubiw, and Maheshwari (Algorithmica 2022) showed that 4/3 ≤ A (2π/3) ≤ 3/2 . In this paper we improve the upper bound and show that A (2π/3) ≤ 13/9.
Patrick Devaney
Computer Science MSc Student
My research interests include computational geometry, graph theory, and optimization.