Bounded-Angle Spanning Tree: Modeling Networks with Angular Constraints

详细信息    查看全文

• 作者：Rom Aschner ; Matthew J. Katz
• 关键词：Wireless networks ; Directional antennas ; Minimum spanning tree ; Approximation algorithms ; NP ; hardness ; Hop spanner ; Power assignment
• 刊名：Algorithmica
• 出版年：2017
• 出版时间：February 2017
• 年：2017
• 卷：77
• 期：2
• 页码：349-373
• 全文大小：
• 刊物类别：Computer Science
• 刊物主题：Algorithm Analysis and Problem Complexity; Theory of Computation; Mathematics of Computing; Algorithms; Computer Systems Organization and Communication Networks; Data Structures, Cryptology and Inform
• 出版者：Springer US
• ISSN：1432-0541
• 卷排序：77

文摘

We introduce a new structure for a set of points in the plane and an angle \(\alpha \), which is similar in flavor to a bounded-degree MST. We name this structure \(\alpha \)-MST. Let P be a set of points in the plane and let \(0 < \alpha \le 2\pi \) be an angle. An \(\alpha \)-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 \(\alpha \). An \(\alpha \)-MST of P is then an \(\alpha \)-ST of P of minimum weight, where the weight of an \(\alpha \)-ST is the sum of the lengths of its edges. For \(\alpha < \pi /3\), an \(\alpha \)-ST does not always exist, and, for \(\alpha \ge \pi /3\), it always exists (Ackerman et al. in Comput Geom Theory Appl 46(3):213–218, 2013; Aichholzer et al. in Comput Geom Theory Appl 46(1):17–28, 2013; Carmi et al. in Comput Geom Theory Appl 44(9):477–485, 2011). In this paper, we study the problem of computing an \(\alpha \)-MST for several common values of \(\alpha \). Motivated by wireless networks, we formulate the problem in terms of directional antennas. With each point \(p \in P\), we associate a wedge \({\textsc {w}_{p}}\) of angle \(\alpha \) and apex p. The goal is to assign an orientation and a radius \(r_p\) to each wedge \({\textsc {w}_{p}}\), such that the resulting graph is connected and its MST is an \(\alpha \)-MST (we draw an edge between p and q if \(p \in {\textsc {w}_{q}}\), \(q \in {\textsc {w}_{p}}\), and \(|pq| \le r_p, r_q\)). We prove that the problem of computing an \(\alpha \)-MST is NP-hard, at least for \(\alpha =\pi \) and \(\alpha =2\pi /3\), and present constant-factor approximation algorithms for \(\alpha = \pi /2, 2\pi /3, \pi \). One of our major results is a surprising theorem for \(\alpha = 2\pi /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 independently, such that the graph induced by P is connected. We apply the theorem to the antenna conversion problem and to the orientation and power assignment problem.