Complexity of counting regions in hyperplane arrangements

Question

Let $H_1,\ldots,H_n$ be hyperplanes in $\Bbb R^d$. Denote $\mathcal{H} :=\{H_1,\ldots,H_n\}$ and let $c(\mathcal{H})$ be the number of regions in the complement: $\Bbb R^d\setminus \bigcup H_i$.

Question: What is the complexity of computing $c(\mathcal{H})$?

Here we are assuming that $H_i$ are defined explicitly over $\Bbb Q$, and that the dimension $d$ is NOT bounded. For a fixed $d$ there is plenty of literature, see e.g. Halperin-Sharir Arrangements survey. As far as I can tell, none of that literature is applicable.

Note that for graphical arrangements $\{x_i-x_j=0 : (ij)\in E\}$ corresponding to the graph $G=([n],E)$, the number of regions $c(\mathcal H)$ is an evaluation of the chromatic (and therefore Tutte) polynomial, and thus #P-hard. See e.g. Welsh's ``Complexity: knots, colouring and counting'' book, Chapter 6.

Comment: It feels like this should be well known, so maybe this is a reference request. The problem is in PSPACE and feels similar to $\exists \Bbb R$ (see Wikipedia page), except it's a counting problem. Is it $\exists \Bbb R$-hard, for example?

Answer 1

The problem is $\#\mathsf{P}$-complete. As you already noted, the problem is $\#\mathsf{P}$-hard even when we restrict to graphical arrangements, so it remains to show that the problem is in $\#\mathsf{P}$. Directly from the definition of $\#\mathsf{P}$, we see that it suffices to show that we can give a short description of a region of a given arrangement whose regionhood can be verified in polynomial time. Every region has a set of facets, so we can describe a region by a linear program that lists the facets and specifies on which side of the facet the region lies. To verify that an alleged region really is a region, we need to check that (a) the linear program has a solution; (b) the solution set is full-dimensional; (c) for every hyperplane $H$ in the arrangement not listed as a facet, one of the two constraints "above $H$" and "below $H$" would be redundant if added to the linear program. The theory of linear programming tells us that all these checks can be performed in polynomial time. For example, for part (b), we can check, for each coordinate direction $x_i$, that maximizing $x_i$ and minimizing $x_i$ yield different answers.