Establishing strong connectivity using optimal radius half-disk antennas

Given a set S of points in the plane representing wireless devices, each point equipped with a directional antenna of radius r and aperture angle α≥180°, our goal is to find orientations and a minimum r for these antennas such that the induced communication graph is strongly connected. We show that r=3 if α∈[180°,240°), r=2 if α∈[240° ,270°), r=2sin(36°) if α∈[270°,288°), and r=1 if α≥288° suffices to establish strong connectivity, assuming that the longest edge in the Euclidean minimum spanning tree of S is 1. These results are worst-case optimal and match the lower bounds presented in [I. Caragiannis, C. Kaklamanis, E. Kranakis, D. Krizanc, A. Wiese, Communication in wireless networks with directional antennae, in: Proc. of the 20th Symp. on Parallelism in Algorithms and Architectures, 2008, pp. 344-351]. In contrast, r=2 is sometimes necessary when α