Establishing strong connectivity using optimal radius half-disk antennas
Greg Aloupis, Mirela Damian, Robin Y. Flatland, Matias Korman, Özgür Özkan, David D. Rappaport, Stefanie Wuhrer · 2011
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 suffices to establish strong connectivity, assuming that the longest edge in the Euclidean minimum spanning tree for S is 1. This result is optimal in the sense that r = √ 3 is necessary in the worst-case for α ∈ [180°; 240°). In contrast, r = 2 is sometimes necessary when α < 180°.