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

To obtain this result, we devise an O(n)-time algorithm that, given any Hamiltonian path $\varPi$ of P, constructs a $\frac{2\pi }{3}$-ST  $\mathcal{T}$ of P, such that $\mathcal{T}$’s weight is at most twice that of $\varPi$ and, moreover, $\mathcal{T}$ is a 3-hop spanner of $\varPi$. This latter result is optimal in the sense that for any ${\varepsilon }> 0$ there exists a polygonal path for which every $\frac{2\pi }{3}$-ST (of the corresponding set of points) has weight greater than $2-{\varepsilon }$ times the weight of the path.

M. Katz was supported by grant 1884/16 from the Israel Science Foundation.