Bounded-Angle Spanning Tree: Modeling Networks with Angular Constraints

Abstract

We introduce a new structure for a set of points in the plane and an angle $\alpha$, which is similar in flavor to a bounded-degree MST. We name this structure $\alpha$-MST. Let P be a set of points in the plane and let $0 < \alpha \le 2\pi$ be an angle. An $\alpha$-ST of P is a spanning tree of the complete Euclidean graph induced by P, with the additional property that for each point $p \in P$, the smallest angle around p containing all the edges adjacent to p is at most $\alpha$. An $\alpha$-MST of P is then an $\alpha$-ST of P of minimum weight, where the weight of an $\alpha$-ST is the sum of the lengths of its edges. For $\alpha < \pi /3$, an $\alpha$-ST does not always exist, and, for $\alpha \ge \pi /3$, it always exists (Ackerman et al. in Comput Geom Theory Appl 46(3):213–218, 2013; Aichholzer et al. in Comput Geom Theory Appl 46(1):17–28, 2013; Carmi et al. in Comput Geom Theory Appl 44(9):477–485, 2011). In this paper, we study the problem of computing an $\alpha$-MST for several common values of $\alpha$. Motivated by wireless networks, we formulate the problem in terms of directional antennas. With each point $p \in P$, we associate a wedge ${\textsc {w}_{p}}$ of angle $\alpha$ and apex p. The goal is to assign an orientation and a radius $r_p$ to each wedge ${\textsc {w}_{p}}$, such that the resulting graph is connected and its MST is an $\alpha$-MST (we draw an edge between p and q if $p \in {\textsc {w}_{q}}$, $q \in {\textsc {w}_{p}}$, and $|pq| \le r_p, r_q$). We prove that the problem of computing an $\alpha$-MST is NP-hard, at least for $\alpha =\pi$ and $\alpha =2\pi /3$, and present constant-factor approximation algorithms for $\alpha = \pi /2, 2\pi /3, \pi$. One of our major results is a surprising theorem for $\alpha = 2\pi /3$, which, besides being interesting from a geometric point of view, has important applications. For example, the theorem guarantees that given any set P of 3n points in the plane and any partitioning of the points into n triplets, one can orient the wedges of each triplet independently, such that the graph induced by P is connected. We apply the theorem to the antenna conversion problem and to the orientation and power assignment problem.