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°α⩾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°)α∈[180°,240°), r=2 if α∈[240°,270°)α∈[240°,270°), r=2sin(36°)r=2sin(36°) if α∈[270°,288°)α∈[270°,288°), and r=1r=1 if α⩾288°α⩾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=2r=2 is sometimes necessary when α<180°α<180°.