Return to 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 \cup 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?

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?

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 \cup 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 NP-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?

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 \cup 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?

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 \cup 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 NP-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$, except it's a counting problem. Is it $\exists \Bbb R$-hard, for example?

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 \cup 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 NP-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?