Suppose we have an arrangement $mathcal{A}$ of $n$ geometric objects $x_1, dots, x_n subseteq mathbb{R}^2$ in the plane, with a distinguished point $p_i$ in each object $x_i$. The generalized transmission graph of $mathcal{A}$ has vertex set ${x_1, dots, x_n}$ and a directed edge $x_ix_j$ if and only if $p_j in x_i$. Generalized transmission graphs provide a generalized model of the connectivity in networks of directional antennas. The complexity class $exists mathbb{R}$ contains all problems that can be reduced in polynomial time to an existential sentence of the form $exists x_1, dots, x_n: phi(x_1,dots, x_n)$, where $x_1,dots, x_n$ range over $mathbb{R}$ and $phi$ is a propositional formula with signature $(+, -, cdot, 0, 1)$. The class $exists mathbb{R}$ aims to capture the complexity of the existential theory of the reals. It lies between $mathbf{NP}$ and $mathbf{PSPACE}$. Many geometric decision problems, such as recognition of disk graphs and of intersection graphs of lines, are complete for $exists mathbb{R}$. Continuing this line of research, we show that the recognition problem of generalized transmission graphs of line segments and of circular sectors is hard for $exists mathbb{R}$. As far as we know, this constitutes the first such result for a class of directed graphs.
Download