2
$\begingroup$

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?

$\endgroup$
  • 4
    $\begingroup$ I noticed you posted copies of this question at cstheory.stackexchange.com/q/32275/5204, math.stackexchange.com/q/1395844/11268. Posting the same question on multiple SE sites is discouraged because it leads to duplication of efforts as people try to answer the question on one site, unaware of any other answers/efforts on the other. The etiquette is that you pick one site, and post just there, with the exception that if the question stays up with no good responses for maybe a week, then it's okay to cross-post. Mostly this is to prevent people accidentally wasting time. $\endgroup$ – Kirill Aug 17 '15 at 18:37
  • $\begingroup$ This seems like a difficult problem to me. Can't you compare the moments of the vertices of the convex hulls? It does not check that $P=Q$, but $P\neq Q$. $\endgroup$ – nicoguaro Aug 17 '15 at 21:41
  • $\begingroup$ Yes but it doesn't say anything about the complexity of the problem. $\endgroup$ – Star Aug 17 '15 at 21:49
  • $\begingroup$ I thought that you had an application in mind. Although this seem more theoretical... I will write some thoughts as an answer. $\endgroup$ – nicoguaro Aug 18 '15 at 3:21
  • $\begingroup$ I'm voting to close this question as off-topic because this question is a cross-post, and probably a better fit on CSTheory Stack Exchange, where it has been cross-posted. $\endgroup$ – Geoff Oxberry Aug 19 '15 at 17:16
0
$\begingroup$

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)$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ This is a good idea but still does not tell anything about the worst case complexity. Rather, it proposes an exponential algorithm. $\endgroup$ – Star Aug 18 '15 at 7:23
  • $\begingroup$ I think that I considered the worst case scenario. What do you mean by complexity then? $\endgroup$ – nicoguaro Aug 18 '15 at 13:04
  • $\begingroup$ As far as I see, your approach gives an exponential algorithm as the time complexity depends on the number of vertices of both polytopes. I would like to see if the problem is in P or it is NP-hard. $\endgroup$ – Star Aug 18 '15 at 13:07
  • 1
    $\begingroup$ If that's what you want, you should mention it on your question, we can't just read your mind. I suppose it is exponential in $n$, but you never mentioned that either. $\endgroup$ – nicoguaro Aug 18 '15 at 13:12

Not the answer you're looking for? Browse other questions tagged or ask your own question.