Is there a way to numerically check if two halfspaces defined by two planes intersect?

Question

Forgive me for potential naming errors, but here is my question.

Let's say that we have two planes defined with following equations:

$$ a_1x_1 + a_2x_2 + a_3x_3 = c $$ $$ b_1x_1 + b_2x_2 + b_3x_3 = d $$

A thing to note is that $x_1, x_2, x_3 \in [\alpha, \beta]$

The first plane potentially halves the cube $[\alpha,\beta]^3$ in two halfspaces: $H_{1,+}=\{(x_1,x_2,x_3) \in [\alpha,\beta]^3 : a_1x_1+a_2x_2+a_3x_3-d \geq 0 \}$ and $H_{1,-}=\{(x_1,x_2,x_3) \in [\alpha,\beta]^3 : a_1x_1+a_2x_2+a_3x_3-d < 0 \}$.

The second plane does the same thing and potentially defines two halfspaces: $H_{2,+}$ and $H_{2,-}$.

Is there a way to numerically check, for example, if $H_{1,+} \cap H_{2,-} \neq \emptyset$, i.e. to check this without drawing planes and the cube in 3D?

Answer 1

First of all find the intersection points between plane 1 and the edges of the cube: these are the vertices of a polygon, which is the intersection between plane 1 and the cube.

Then check if all the vertices of that polygon belong to the same halfspace of plane 2: if so, then the cube is divided into three regions, two halfspaces don't intersect (it is easy to find out which ones) and the other do.

If, on the other hand, the vertices of the polygon belong to both halfplanes, then the cube is divided into four regions and all halfspaces intersect.

I'm not considering the special case when one of the planes is "tangent" to the cube (i.e. they have in common only a vertex, or an edge, or a face), but it is not difficult to deal with it.

EXAMPLE.

Take $[0,1]^3$ with two planes: $x+y+z={1\over2}$ (plane 1) and $x+y={3\over2}$ (plane 2). The intersections between plane 1 and the edges of the cube are points $A=\big({1\over2},0,0\big)$, $B=\big(0,{1\over2},0\big)$, $C=\big(0,0,{1\over2}\big)$.

Function $x+y-{3\over2}$ is negative at all three points, so all of plane 1 lies inside $H_{2,-}$. On the other hand, $P=\big(1,{1\over2},0\big)$ is a point of space 2, and function $x+y+z-{1\over2}$ is positive at $P$, so all of plane 2 lies inside $H_{1,+}$. We have then $H_{2,+}\cap H_{1,-}=\emptyset$, while all the other couples of halfplanes intersect.

Answer 2

We would like to determine whether the intersection of the two half-spaces

$$a_{11} x_1 + a_{12} x_2 + a_{13} x_3 \geq b_1$$

$$a_{21} x_1 + a_{22} x_2 + a_{23} x_3 < b_2$$

with the cube $[\alpha,\beta]^3$ is empty. Multiplying both sides of the 2nd inequality by $-1$ and replacing the strict inequality with a non-strict one, we can decide whether the intersection is empty by solving the following linear program (LP)

$$\begin{array}{ll} \text{minimize} & 0_3^{\top} \mathrm x\\ \text{subject to} & \begin{bmatrix} a_{11} & a_{12} & a_{13}\\ -a_{21} & -a_{22} & -a_{23}\end{bmatrix} \mathrm x \geq \begin{bmatrix} b_1\\ - b_2\end{bmatrix}\\ & \alpha 1_3 \leq \mathrm x \leq \beta 1_3\end{array}$$

where the objective function is zero because we are only interested in deciding feasibility.

Let $\mathrm x^*$ be the solution produced by the LP solver. If

$$a_{21} x_1^* + a_{22} x_2^* + a_{23} x_3^* = b_2$$

then we have to ponder whether this solution is admissible or not.