Connectivity guarantees for wireless networks with directional antennas (Q654284)

Let us consider a set \(\mathcal{P}\) of points in the Euclidean plane where each point represents a communication station. Given an angle \(\alpha\), one can place at each node \(v \in \mathcal{P}\) a wedge of angle \(\alpha\), centered at \(v\), representing the emission direction of a high-gain directional antenna. We say that \(u\) sees \(v\) if \(u\) lies in the wedge centered at \(v\). The communication graph is an undirected graph that consists of the node set \(\mathcal{P}\) and the set of edges \(E = \{(u, v) \mid u\;\text{sees}\;v\;\text{and}\;v\;\text{sees}\;u\}\). The authors study the question of connectivity in communication graphs. The first question addresed is: what is the smallest value of the angle \(\alpha\), for which a connected network with directional antennas of \(\alpha\) degrees can be built? It is proven that connected network can be built with antennas of \(60^\circ\). A second problem is to determine wether or not the resulting communication graph contains a Hamiltonian path. By a result of \textit{S.\,P. Fekete} and \textit{G.\,J. Woeginger} [Comput. Geom. 8, No.\,4, 195--218 (1997; Zbl 1133.90385)], this is always possible with antennas of \(60^\circ\). An alternative proof of this statement is presented here which uses paths that tend to have shorter edges and fewer self-crossings than those of Fekete and Woeginger.