3D Convex hull in 3D Convex hull

Question

I have two convex hull, How to check if the smaller one is wholly, partially or not inside the Bigger Convex hull?

Answer 1

The answer depends on the available representation for the two sets. So, let us examine how you can check whether $C_1$ is in $C_2$ in each of the following cases:

Case I. $C_1$: extreme points, $C_2$: halfspaces This is the most trivial case. If $C_1=\mathrm{co}\{x_1, x_2, \ldots, x_n\}$ and $C_2=\{x: Hx\leq K\}$ (where $\leq$ is meant element-wise), then just check whether $Hx_i\leq K$. In this case it is also easy to tell whether $C_1$ is outside $C_2$ or it is neither a subset or a superset and they have a nonempty intersection.

Case II. $C_1$ and $C_2$ are given as a linear transformation of a $\mathcal{B}_{\infty}$ with $A,B\in\mathbb{R}^{m\times n}$ and $C_1=A \mathcal{B}_\infty$ and $C_2=B\mathcal{B}_\infty$ (where $\mathcal{B}_\infty=\{x: \|x\|_\infty\leq 1\}$). Then $C_1\subseteq C_2$ if and only if $\|A'x\|_1\leq \|B'x\|_1$ for all $x\in\mathbb{R}^m$. However, this condition cannot always be reduced to something simpler unless, for example, $m=n$, when it can be equivalently written as $\|A B^\dagger\|\leq 1$, where $B^\dagger$ is the Moore-Penrose pseudoinverse of $B$.

Proof. Let us denote by $\delta^*(x\mid C)$ the support function of a set $C$, that is $\delta^*(x\mid C) = \sup_{y\in C}x'y$. Since $A\mathcal{B}_\infty$ and $B\mathcal{B}_\infty$ are both convex and closed, we have

$$ \begin{aligned} A\mathcal{B}_\infty &\subseteq B\mathcal{B}_\infty\\ \Leftrightarrow \delta^*(x\mid A\mathcal{B}_\infty) &\leq \delta^*(x\mid B\mathcal{B}_\infty)\\ \Leftrightarrow \sup\{x'As\mid x\in \mathcal{B}_\infty\} &\leq \sup\{x'Bp\mid p\in \mathcal{B}_\infty\}\\ \Leftrightarrow \sup_{\|s\|_\infty\leq 1} x'As &\leq \sup_{\|p\|_\infty\leq 1} x'Bp \end{aligned} $$ which completes the proof.

Now note that in this particular case, the two sets cannot be disjoint, so it the above condition fails, they will not be nested but they will have a nonempty intersection.

Case III. $C_1$ and $C_2$ are given linear transformations of a ball Similarly as above we may prove that $A\mathcal{B}\subseteq B\mathcal{B}$ if and only if $\|A'x\|_*\leq \|B'x\|_*$ where $\|\cdot\|_*$ is the dual norm of $\|\cdot\|$ which defines $\mathcal{B}=\{x: \|x\|\leq 1\}$.

Case IV. Equal number of extreme points. In that case we may apply the following result (source: Lemma 4.5.1 in L.Q. Thuan, Piecewise affine dynamical systems: well-posedness, controllability and stabilizability, PhD dissertation, Uni. Groningen, 2013): Let $H_P,H_Q\in \mathbb{R}^n$ has full row rank and let $P=\{x: H_P x\leq K_P\}$ and $Q=\{x: H_Q x\leq K_Q\}$. Then $P\subseteq Q$ if and only if one of the following holds true:

1. There is a lower triangular matrix $M$ with positive diagonal elements so that $H_P = MH_Q$ and $K_P=MK_Q$.
2. There is an $1\leq l \leq m $ and a matrix $M\in\mathbb{R}^{l\times l}$ so that $H_P^{[l]}=MH_Q^{[l]}$ and $K_P^{[l]}<MK_Q^{[l]}$, where $H_P^{[l]}$ stands for the matrix formed by the first $l$ rows of $H_P$.

Case V If both sets are given in the form of an intersection of subspaces, then it is not always easy - or computationally tractable - to judge whether one is contained in the other. Then, one may have to resort to the enumeration of the vertices of $C_1$ to tell whether $C_1\subseteq C_2$.

Case VI If both sets are represented by a set of extreme points, then again it is very difficult to tell whether one is contained in the other, but it is somewhat easier to tell whether the convex sets these points define are disjoint: simply find a line that separates the points by least squares.

Answer 2

According to the definition of a "convex hull" as the intersection of multiple Half-Spaces, it should be sufficient to check whether all corners of one convex hull are contained in the other.

A point is contained in a convex hull if and only if it is "on the same side" of all planes that make up the faces of the convex hull. So when you want to check whether one point is contained in the convex hull, you can compute the dot products of the point and the normals of the faces of the convex hull. If they are all positive (or negative, depending on the orientation of the faces), then the point is contained in the convex hull.

You can do this for all points (corners) of the smaller convex hull:

• If they are all contained in the larger convex hull, then the smaller one is completely contained in the larger one.
• If they are all not contained in the larger convex hull, then the smaller one is completely outside in the larger one.
• Otherwise, the convex hulls are intersecting