Determine if a rectangular solid is within polyhedron?

tashirosgt · **Posted:** Fri, 1 Apr 2011 15:52:41 UTC

Find an efficient set of constraints that determine whether an axis-aligned rectangular solid is inside a polyhedron. Be more economical than writing constraints that say each corner of the rectangular solid is inside it.

I found a solution to this problem on the web, but there was no proof of the answer. Can anyone explain why the following constraints would work?

Let $\mathbf{u}$ and $\mathbf{l}$ be

dimensional vectors with $\mathbf{u} < \mathbf{l}$ ( The "

" means a component-by-component relation.) Let $\mathbf{R}$ be the rectangular solid defined by the vectors $\{ {\mathbf{x} : \mathbf{l} \leq \mathbf{x} \leq \mathbf{u} \}$ (So $\mathbf{l}$ is the "lower corner" and $\mathbf{u}$ is the "upper" corner). Let $\mathbf{P}$ be the polyhedron defined by the set of vectors
$\{ \mathbf{x}: \mathbf{A} \mathb{x} \leq \mathbf{b}\}$ where $\mathbf{A}$ is a given matrix with

row entries and $\mathbf{b}$ is a given vector of the same column dimension as $\mathbf{A}$ .

Define $\mathbf{A^+}$ to be the matrix with entries $\mathbf{A}^+_{i,j} = max\{ \mathbf{A}_{i,j}, 0\}$ .

Define $\mathbf{A^-}$ to be the matrix with entries $\mathbf{A}^-_{i,j} = max\{ -\mathbf{A}_{i,j}, 0\}$ .

$\mathbf{R} \subseteq \mathbf{P}$ iff $\mathbf{A^}^+ \mathbf{u} - \mathbf{A}^- \mathbf{l} \leq \mathbf{b}$

outermeasure · **Posted:** Fri, 1 Apr 2011 16:46:59 UTC

tashirosgt wrote:

Find an efficient set of constraints that determine whether an axis-aligned rectangular solid is inside a polyhedron. Be more economical than writing constraints that say each corner of the rectangular solid is inside it.

I found a solution to this problem on the web, but there was no proof of the answer. Can anyone explain why the following constraints would work?

Let $\mathbf{u}$ and $\mathbf{l}$ be

dimensional vectors with $\mathbf{u} < \mathbf{l}$ ( The "

" means a component-by-component relation.) Let $\mathbf{R}$ be the rectangular solid defined by the vectors $\{ {\mathbf{x} : \mathbf{l} \leq \mathbf{x} \leq \mathbf{u} \}$ (So $\mathbf{l}$ is the "lower corner" and $\mathbf{u}$ is the "upper" corner). Let $\mathbf{P}$ be the polyhedron defined by the set of vectors
$\{ \mathbf{x}: \mathbf{A} \mathb{x} \leq \mathbf{b}\}$ where $\mathbf{A}$ is a given matrix with

row entries and $\mathbf{b}$ is a given vector of the same column dimension as $\mathbf{A}$ .

Define $\mathbf{A^+}$ to be the matrix with entries $\mathbf{A}^+_{i,j} = max\{ \mathbf{A}_{i,j}, 0\}$ .

Define $\mathbf{A^-}$ to be the matrix with entries $\mathbf{A}^-_{i,j} = max\{ -\mathbf{A}_{i,j}, 0\}$ .

$\mathbf{R} \subseteq \mathbf{P}$ iff $\mathbf{A^}^+ \mathbf{u} - \mathbf{A}^- \mathbf{l} \leq \mathbf{b}$

I think you want $\mathbf{l}<\mathbf{u}$ instead of the other way round (otherwise your cuboid is empty).

The left hand side of each constraint $A_i^+u-A^-_il\leq b_i$ is the largest possible A_iv

as v ranges over the vertices $v_j=u_j\text{ or }l_j$ , by the choice of A^+ and A^- (if the coefficient is negative, choose the lower so it subtracts less, and if the coefficient is positive, choose the upper so it adds more).

S.O.S. Mathematics CyberBoard

Determine if a rectangular solid is within polyhedron?

Who is online