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!

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ Once again, check this out cis.upenn.edu/~cis610/sp06stanley.pdf $\endgroup$
    – T. Amdeberhan
    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$
    – Dima Pasechnik
    Commented Jan 1, 2017 at 19:10
  • $\begingroup$ @DimaPasechnik thanks, corrected. And the answer is yes $\endgroup$
    – AvidLearner
    Commented Jan 1, 2017 at 19:17
  • $\begingroup$ @T.Amdeberhan can you please point out which is the relevant section? $\endgroup$
    – AvidLearner
    Commented Jan 5, 2017 at 14:26

1 Answer 1

Reset to default
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$.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .