Computing the Pontryagin set difference for vertex representation The Minkowski set addition for two polyhedra
$ A \oplus B  = \{ a+b|a \in A, b \in B \}$
is fairly simple to implement with the vertex representation by just summing up all the points, I'll get some points that are not actually vertices, but they are in the interior of the sum and don't cause problems.
However, when I want to implement the Pontryagin set difference,
$A \ominus B = \{ a|a+ B \subseteq A \}$,
simply subtracting points leads to wrong results.
Is it possible to implement the Pontryagin set difference for the vertex representations of two Polyhedra and if, how do I do it?
(feel free to add or change tags if necessary, I wasn't sure about that)
 A: It is true that Minkowski sums are easy to compute in the vertex representation. However, the Pontryagin difference is not that straightforward to compute in vertex represntation. This is because the Pontryagin difference preserves the number of hyperplanes in the set $A$, and can be defined exactly using the hyperplane representation.
That is, given polytopes
$$A := \{ a \: | \: Y_A a \le z_A \}, \quad B := \{b \: | \: Y_B b \le z_B \}, $$
the set $C:= A \ominus B$ has the representation
$$ C = \{c \: |\: Y_A c \le z_A - t_B \}, $$
where the $j^{th}$ element of $t_B$ is computed by the maximization
$$[t_B]_j:= \max_{b \in B}  [Y_A]_j b $$.
The set $C$ defined above is the exact polytope which you would like to find. However, you start with a vertex representation of $A$. Even MPT3 solves this problem by first converting the polytopes $A$ and $B$ into hyperplane representation, and obtaining $C$ in hyperplane form. If you then want a vertex representation of $C$, you will then have to compute it explicitly. Note that switching between hyperplane and vertex forms is a challenging problem (See Generating All Vertices of a Polyhedron Is Hard, and A Survey and Comparison of Methods for Finding All Vertices of Convex Polyhedral Sets).
In essence, the problem you describe cannot directly be solved yet for generic polytopes $A$ and $B$. Maybe this operation can be performed efficiently for special cases.
A: If you have access to matlab, use the MPT3 toolbox. More specifically, use the minus command.
