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

• Published in: arXiv.org 2020-10
• Main Authors: Ashur, Stav, Katz, Matthew J
• Format: Article
• Language: English
• Subjects: Algorithms; Approximation; Directional antennas; Graph theory; Mathematical analysis; Minimum weight; Polygons; Wireless networks
• ISSN: 2331-8422

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,\ldots,p_n\}\) be a set of \(n\) points in the plane, let \(\Pi\) be the polygonal path \((p_1,\ldots,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\, \({\cal T}\) of \(P\), such that \({\cal T}\)'s weight is at most twice that of \(\Pi\) and, moreover, \({\cal T}\) is a 3-hop spanner of \(\Pi\). 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 has weight greater than \(2-\varepsilon\) times the weight of the path.