Checking equivalence of two polytopes

Question

Consider a vector of variables $\vec{x}$, and a set of linear constraints specified by $A\vec{x}\leq b$.

Furthermore, consider two polytopes

$$\begin{align*} P_1&=\{(f_1(\vec{x}), \cdots, f_m(\vec{x}))\mid A\vec{x}\leq b\}\\ P_2&=\{(g_1(\vec{x}), \cdots, g_m(\vec{x}))\mid A\vec{x}\leq b\} \end{align*}$$

where $f$'s and $g$'s are affine mappings. Namely, they are of the form $\vec{c}\cdot \vec{x} +d$. (We note that $P_1$ and $P_2$ are polytopes because they are "affine mappings" of the polytope $A\vec{x}\leq b$.)

The question is, how to decide whether $P_1$ and $P_2$ are equal as sets? What's the complexity?

The motivation of the problem is from sensor networks, but it seems to be a lovely (probably basic?) geometry problem. One can solve this in exptime, possibly by enumerating all the vertices of $P_1$ and $P_2$, but is there a better approach?

Answer 1

I cannot say for sure if you will consider the following approach as better, but from a complexity-theoretic point of view there is a more efficient solution. The idea is to rephrase your question in the first-order theory of the rationals with addition and order. You have that $P_1$ is included in $P_2$ if and only if \begin{align*} \Phi := \forall \vec{x}.\exists \vec{y}.\left( A \cdot \vec{x} \le b \implies \left( A \cdot \vec{y} \le b \wedge \bigwedge_{1\le i\le m} f_i(\vec{x}) = g_i(\vec{y}) \right)\right) \end{align*} is valid. It is clear how to derive equivalence of $P_1$ and $P_2$ in the same way. Now $\Phi$ has a fixed quantifier-alternation prefix, and is consequently decidable in $\Pi_2^\text{P}$, the second level of the polynomial-time hierarchy (Sontag, 1985). I'm pretty confident that it is possible to also prove a matching lower bound, I recall reading somewhere that inclusion between two polytopes is $\Pi_2^\text{P}$-hard.

If you are looking for tool support in order to solve such problems in practice, modern SMT-solvers such as z3 fully support this theory.

Answer 2

The fact that the underlying polytope $Ax \le b$ is the same for $P_1$ and $P_2$ does not matter, unless we know something specific about $A$ and $b$. This is because a general polytope is an affine projection of a simplex (see, for instance, Ziegler's "Lectures for Polytopes", Theorem 2.15). Thus, if $A$ and $b$ encode a simplex, your question is equivalent to asking how hard general polytope isomorphism is. A quick search reveals the following paper by Kaibel and Schwartz On the Complexity of Polytope Isomorphism Problems, where they show that it is Graph Isomorphism hard.