2015/02/16 by Paz Carmi, Carmi, Paz, Lilach Chaitman-Yerushalmi +1
Computer Science · #Computational Geometry (cs.CG) #Computational Geometry and Mesh Generation #FOS: Computer and information sciences #Mobile Ad Hoc Networks #Optimization and Search Problems #cs.CG
paper · pdf · doi:10.48550/arxiv.1502.04533
arxiv created 2015/02/16 · openalex publication_date 2015/02/16 · arxiv updated 2015/02/17 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We study the problem of assigning transmission ranges to radio stations placed arbitrarily in a d-dimensional (d-D) Euclidean space in order to achieve a strongly connected communication network with minimum total power consumption. The power required for transmitting in range r is proportional to rα, where α is typically between 1 and 6, depending on various environmental factors. While this problem can be solved optimally in 1D, in higher dimensions it is known to be NP-hard for any α≥ 1. For the 1D version of the problem, i.e., radio stations located on a line and α≥ 1, we propose an optimal O(n2)-time algorithm. This improves the running time of the best known algorithm by a factor of n. Moreover, we show a polynomial-time algorithm for finding the minimum cost range assignment in 1D whose induced communication graph is a t-spanner, for any t ≥ 1. In higher dimensions, finding the optimal range assignment is NP-hard; however, it can be approximated within a constant factor. The best known approximation ratio is for the case α=1, where the approximation ratio is 1.5. We show a new approximation algorithm with improved approximation ratio of 1.5-ε, where ε>0 is a small constant.