2014/02/25 by Rom Aschner, Aschner, Rom, Matthew J. Katz +1 · 1 citation
Computer Science · Engineering · #Computational Geometry (cs.CG) #Computational Geometry and Mesh Generation #FOS: Computer and information sciences #Networking and Internet Architecture (cs.NI) #Optimization and Packing Problems #Vehicle Routing Optimization Methods #cs.CG #cs.NI
paper · pdf · doi:10.48550/arxiv.1402.6096
arxiv created 2014/02/25 · openalex publication_date 2014/02/25 · arxiv updated 2014/02/26 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We introduce a new structure for a set of points in the plane and an angle α, which is similar in flavor to a bounded-degree MST. We name this structure α-MST. Let P be a set of points in the plane and let 0 < α≤ 2π be an angle. An α-ST of P is a spanning tree of the complete Euclidean graph induced by P, with the additional property that for each point p ∈ P, the smallest angle around p containing all the edges adjacent to p is at most α. An α-MST of P is then an α-ST of P of minimum weight. For α< π/3, an α-ST does not always exist, and, for α≥ π/3, it always exists. In this paper, we study the problem of computing an α-MST for several common values of α. Motivated by wireless networks, we formulate the problem in terms of directional antennas. With each point p ∈ P, we associate a wedge Wp of angle α and apex p. The goal is to assign an orientation and a radius rp to each wedge Wp, such that the resulting graph is connected and its MST is an α-MST. (We draw an edge between p and q if p ∈ Wq, q ∈ Wp, and |pq| ≤ rp, rq.) Unsurprisingly, the problem of computing an α-MST is NP-hard, at least for α=π and α=2π/3. We present constant-factor approximation algorithms for α= π/2, 2π/3, π. One of our major results is a surprising theorem for α= 2π/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 \em independently, such that the graph induced by P is connected. We apply the theorem to the \em antenna conversion problem.