# Affine Hyperplane Arrangements in $\mathbb R^d$

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!

• Once again, check this out cis.upenn.edu/~cis610/sp06stanley.pdf Commented Jan 1, 2017 at 18:11
• a representative from the interior of each region (the latter are not subspaces, by the way, they are merely convex polyhedra) ? Commented Jan 1, 2017 at 19:10
• @DimaPasechnik thanks, corrected. And the answer is yes Commented Jan 1, 2017 at 19:17
• @T.Amdeberhan can you please point out which is the relevant section? Commented Jan 5, 2017 at 14:26

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$.