A 4-Approximation of the $\frac{2\pi }{3}$-MST

Abstract

Bounded-angle (minimum) spanning trees were first introduced in the context of wireless networks with directional antennas. They are reminiscent of bounded-degree spanning trees, which have received significant attention. Let $P=\{p_1,\dots ,p_n\}$ be a set of $n$ points in the plane, let $\Pi$ be the polygonal path $(p_1,\dots ,p_n)$, and let $0<\alpha <2\pi$ be an angle. An $\alpha$-spanning tree ($\alpha$-ST) of $P$ is a spanning tree of the complete Euclidean graph over $P$, with the following property: For each vertex $p_i\in P$, the (smallest) angle that is spanned by all the edges incident to $p_i$ is at most $\alpha$. An $\alpha$-minimum spanning tree ($\alpha$-MST) is an $\alpha$-ST of $P$ of minimum weight, where the weight of an $\alpha$-ST is the sum of the lengths of its edges. In this paper, we consider the problem of computing an $\alpha$-MST, for the important case where $\alpha =\frac{2\pi }{3}$. We present a simple 4-approximation algorithm, thus improving upon the previous results of Aschner and Katz and Biniaz et al., who presented algorithms with approximation ratios 6 and $\frac{16}{3}$, respectively. In order to obtain this result, we devise a simple $O(n)$-time algorithm for constructing a $\frac{2\pi }{3}$-ST\, $\mathcal{T}$ of $P$, such that $\mathcal{T}$'s weight is at most twice that of $\Pi$ and, moreover, $\mathcal{T}$ is a 3-hop spanner of $\Pi$. This latter result is optimal in the sense that for any $\epsilon >0$ there exists a polygonal path for which every $\frac{2\pi }{3}$-ST has weight greater than $2-\epsilon$ times the weight of the path.