Date of Award

6-1-2023

Publication Type

Thesis

Degree Name

M.Sc.

Department

Computer Science

Keywords

antennas;approximation algorithm;bounded angle MST;Euclidean graph;minimum spanning tree (MST);wireless communication networks

Supervisor

Ahmad Biniaz

Supervisor

Prosenjit Bose

Rights

info:eu-repo/semantics/openAccess

Creative Commons License

Creative Commons Attribution 4.0 International License
This work is licensed under a Creative Commons Attribution 4.0 International License.

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 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.

Download

Share

COinS