Consider $\mathcal A=(u_i)_{i=1}^m $ to be a set of hyperplanes in $\mathbb R^d$, such that for every $1\leq i \leq m$: $u_i \in \mathbb R^d$.
These hyperplanes are disconnecting $\mathbb R^d$ to convex polyhedra that are called regions. My question is the following: is there a way to find a representative from each such region?
Thanks!
A naive way to find representatives is to solve $2^m$ systems of linear inequalities. More precisely, you probably want interior points, so your inequalities will be of the form $\langle u_i,x\rangle \geq\epsilon$ for $i\in I$ and $\langle u_j,x\rangle \leq-\epsilon$ for $j\not\in I$, and you will be maximising $\epsilon$ subject to these linear constraints (for each $I\subseteq \{1...m \}$).
For unbounded regions you would need a little more effort: whenever you recognise unbounded case, you augment your linear program as $1\geq \langle u_i,x\rangle \geq\epsilon$ for $i\in I$ and $-1\leq \langle u_j,x\rangle \leq-\epsilon$ for $j\not\in I$.
