1
$\begingroup$

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!

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

1 Answer 1

3
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.