Approximating Average Bounded-Angle Minimum Spanning Trees

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 in 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 avg-α-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 (avg-α-MST) is an α-ST with minimum total edge length. We first focus on α = 2π/3. Let A(α) be the smallest ratio of the length of the avg-α-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. We improve the upper bound and show that A(2π/3) ≤ 13/9. We then generalize the lower bound argument of Biniaz et al. (Algorithmica 2022) for A(2π/3) to a formula giving a lower bound on A(α) for any α ≤π. We further show how to modify the algorithm of Biniaz et al. (Algorithmica 2022) for the avg-2π/3-MST to compute the avg-π-MST, and show that A(π) = 1. Finally, we present an algorithm to compute the avg-π/2-MST, and show that 3/2 ≤ A(π/2) ≤ 4.

Name thesis:degree_name

M.Sc.

Level thesis:degree_level

Masters

Discipline thesis:degree_discipline

Computer Science

Grantor

University of Windsor

Year dc:date.issued

2023

Author dc:creator

• Devaney, Patrick Stephen

Advisors dc:contributor.advisor

• Biniaz, Ahmad
• Bose, Prosenjit

Contributors dc:contributor

• scholarship@uwindsor.ca

Licence

• http://creativecommons.org/licenses/by-nc-nd/4.0/

Language dc:language.iso

en_CA

Handle dc:identifier.uri

https://hdl.handle.net/20.500.14776/9638

OAI identifier oai:identifier

oai:uwindsor.scholaris.ca:20.500.14776/9638