If i have two polytopes denoted by $P_1, P_2 \subset \mathbb{R}^d$, suppose their halfspace representations are respectively $H_1x \leq K_1$ and $H_2x \leq K_2$. Now, considering their Minkowski sum, namely $H_1 \oplus H_2$, i ask myself whether their exists an explicit relation between the halfspace representation of $H_1 \oplus H_2$ and the ones of $H_1, H_2$.
Thanks in advance,
Bests.
Let me try to answer this question. According to
H.R. Tiwary, "On the hardness of computing intersection, union and Minkowski sum of polytopes". Discrete & Computational Geometry, p. 469–479, 2008
the problem of enumerating all rows of the matrix representing $H_1\oplus H_2$ is NP-hard. So: No, there is no explicit relation between the $\mathcal{H}$-representation of $H_1\oplus H_2$ and $H_1$ and $H_2$.
However, for computational purposes there are some tricks to cope with this restriction, for example, you could use support functions or symbolic orthogonal projections. The latter gives you an explicit $\mathcal{H}$-representation of a higher dimensional polyhedron whose orthogonal projection is the Minkowski sum $H_1\oplus H_2$.