Paper detail

Bounded-Angle Spanning Tree: Modeling Networks with Angular Constraints

We introduce a new structure for a set of points in the plane and an angle $α$, which is similar in flavor to a bounded-degree MST. We name this structure $α$-MST. Let $P$ be a set of points in the plane and let $0 < α\le 2π$ be an angle. An $α$-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 $α$. An $α$-MST of $P$ is then an $α$-ST of $P$ of minimum weight. For $α< π/3$, an $α$-ST does not always exist, and, for $α\ge π/3$, it always exists. In this paper, we study the problem of computing an $α$-MST for several common values of $α$. Motivated by wireless networks, we formulate the problem in terms of directional antennas. With each point $p \in P$, we associate a wedge $W_p$ of angle $α$ and apex $p$. The goal is to assign an orientation and a radius $r_p$ to each wedge $W_p$, such that the resulting graph is connected and its MST is an $α$-MST. (We draw an edge between $p$ and $q$ if $p \in W_q$, $q \in W_p$, and $|pq| \le r_p, r_q$.) Unsurprisingly, the problem of computing an $α$-MST is NP-hard, at least for $α=π$ and $α=2π/3$. We present constant-factor approximation algorithms for $α= π/2, 2π/3, π$. One of our major results is a surprising theorem for $α= 2π/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 {\em independently}, such that the graph induced by $P$ is connected. We apply the theorem to the {\em antenna conversion} problem.