On the hardness of computing intersection, union and Minkowski sum of polytopes (Q958243): Difference between revisions

For polytopes \(P_1\), \(P_2\subset \mathbb R^d\), the author considers the intersection \(P_1\cap P_2\), the convex hull of the union \(CH(P_1\cup P_2)\) and the Minkowski sum \(P_1 +P_2\). The principal aim is to analyze the algorithmic complexity of performing these operations and providing a nonredundant description of resulting polytopes. For the Minkowski sum, it is demonstrated that enumerating the facets of \(P_1 +P_2\) is \(NP\)-hard if \(P_1\), \(P_2\) are represented by facets, or if \(P_1\) is specified by vertices and \(P_2\) is a polyhedral cone specified by facets. For the intersection, it is demonstrated that computing the facets or the vertices of \(P_1\cap P_2\) is \(NP\)-hard if one of \(P_1\), \(P_2\) is given by vertices and the other by facets. Besides, computing the vertices of \(P_1\cap P_2\) is \(NP\)-hard if \(P_1\), \(P_2\) are represented by vertices. Because of the polar duality, similar results hold for the convex hull of the union of polytopes.