Abstract
Motivated by the connectivity problem in wireless networks with directional antennas, we study boundedangle spanning trees. Let P be a set of points in the plane and let α be an angle. An αST of P is a spanning tree of the complete Euclidean graph on P with the property that all edges incident to each point p ∈ P lie in a wedge of angle α centered at p. We study the following closely related problems for α = 120 degrees (however, our approximation ratios hold for any α ⩾ 120 degrees).
1) The αminimum spanning tree problem asks for an αST of minimum sum of edge lengths. Among many interesting results, Aschner and Katz (ICALP 2014) proved the NPhardness of this problem and presented a 6approximation algorithm. Their algorithm finds an αST of length at most 6 times the length of the minimum spanning tree (MST). By adopting a somewhat similar approach and using different proof techniques we improve this ratio to 16/3.
2) To examine what is possible with nonuniform wedge angles, we define an ̅αST to be a spanning tree with the property that incident edges to all points lie in wedges of average angle α. We present an algorithm to find an ̅αST whose largest edgelength and sum of edge lengths are at most 2 and 1.5 times (respectively) those of the MST. These ratios are better than any achievable when all wedges have angle α. Our algorithm runs in linear time after computing the MST.
BibTeX  Entry
@InProceedings{biniaz_et_al:LIPIcs:2020:12261,
author = {Ahmad Biniaz and Prosenjit Bose and Anna Lubiw and Anil Maheshwari},
title = {{BoundedAngle Minimum Spanning Trees}},
booktitle = {17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020)},
pages = {14:114:22},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771504},
ISSN = {18688969},
year = {2020},
volume = {162},
editor = {Susanne Albers},
publisher = {Schloss DagstuhlLeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/12261},
URN = {urn:nbn:de:0030drops122616},
doi = {10.4230/LIPIcs.SWAT.2020.14},
annote = {Keywords: boundedangle MST, directional antenna, approximation algorithms}
}
Keywords: 

boundedangle MST, directional antenna, approximation algorithms 
Collection: 

17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020) 
Issue Date: 

2020 
Date of publication: 

12.06.2020 