Comparison of convex hulls [closed]

Question

Consider a set of polytopes $P_i : i=1,2,...,k$ each of which has a structure as $P_i:= \{(x_{i1},x_{i2},..., x_{in})\; |\; x_{ij} \in [a_{ij}, b_{ij}] \subseteq [0,1]\}\;\; \text{for all}\;\; j=1,...,n$ and $\sum_j x_{ij}=1$. We define $P= CH (\cup_i P_i)$ where $CH$ stands for the convex hull.

On the other side, we have another set of polytopes $Q_t: t=1,2,..., r$ each of which defined similarly as $Q_t:= \{(y_{t1},y_{t2},..., y_{tn})\; |\; y_{tj} \in [c_{tj}, d_{tj}] \subseteq [0,1]\; \text{for all}\; j=1,...,n \; \text{and} \sum_j y_{tj}=1\}$. Then we define $Q= CH (\cup_t Q_t)$.

Please note that the number of polytopes $P_i$, i.e., k and the number of polytopes $Q_t$, i.e., r are not necessarily equal. However, both polytopes $P_i$ and $Q_t$ are defined in $\mathbb{R}^n$ as above.

Query: Is checking if $P\neq Q$ computationally hard?

Answer 1

I am writing some ideas that came to my mind, so take this answer with a grain of salt.

First, we need to find a way if $P=Q$.

The only thing that comes to my mind is to compute the Hausdorff distance between $P$ and $Q$. Since each one is the convex hull of the union of a finite sets of polytopes, they are polytopes as well. And it would be enough to compute the Hausdorff distance between the two sets of vertices ($v_P$, $v_Q$).

$$\begin{align} &H(v_P, v_Q) = \max\lbrace h(v_P, v_Q), h(v_Q, v_P)\rbrace\\ &h(v_P, v_Q)=\max_{a\in v_P} \min_{b\in v_Q}\; d(v_P, v_Q) \end{align}$$

If the number of vertices is not the same($n(v_P)\neq n(v_Q)$), then the polytopes are different. We are assuming that they are the same then.

I think that the complexity of computing the Hausdorff distance would be $O(n_P n_Q)$, and they would be equal if $H(v_P, v_Q) =0$.

To estimate $n_P$ and $n_Q$ we can consider the worst case scenario, i.e., the convex hull preserve all the vertices from the set of polytopes. Then, if the maximum number of vertices that a polytope has is $M_P$ for $P$ and $M_Q$ for $Q$, we have as estimates

$$n_P = kM_P\quad \text{and}\quad n_Q = r M_Q \enspace .$$

What translates in $O(n_P n_Q) = O(kr M_P M_Q)$. If we take into account the computation of the distance function ("norm"). Then we end up with something like $O(krn M_P M_Q)$.