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

Bounded-angle (minimum) spanning trees were first introduced in the context of wireless networks with directional antennas. They are reminiscent of bounded-degree (minimum) spanning trees, which have received significant attention. Let P be a set of n points in the plane, 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 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.