On the hardness of computing intersection, union and Minkowski sum of polytopes
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.
- \(f\)-vectors of Minkowski additions of convex polytopes
- Extended convex hull
- From the zonotope construction to the Minkowski addition of convex polytopes
- Generating all vertices of a polyhedron is hard
- Geometric algorithms and combinatorial optimization.
- How good are convex hull algorithms?
- scientific article; zbMATH DE number 3637614 (Why is no real title available?)
- scientific article; zbMATH DE number 2008526 (Why is no real title available?)
- scientific article; zbMATH DE number 1446863 (Why is no real title available?)
- Lectures on Polytopes
- Minkowski Addition of Polytopes: Computational Complexity and Applications to Gröbner Bases
- On the complexity of four polyhedral set containment problems
- On the convex hull of the union of certain polyhedra
- On the Newton polytope of the resultant
- The Cayley trick, lifting subdivisions and the Bohne-Dress theorem on zonotopal tilings
- Exact recursive updating of state uncertainty sets for linear SISO systems
- On highly robust efficient solutions to uncertain multiobjective linear programs
- Self-duality of polytopes and its relations to vertex enumeration and graph isomorphism
- Set operations and order reductions for constrained zonotopes
- a-tint: a polymake extension for algorithmic tropical intersection theory
- Economic model predictive control for robust optimal operation of sparse storage networks
- Constrained zonotopes: a new tool for set-based estimation and fault detection
- Verification of Hybrid Systems
- On the hardness of minkowski addition and related operations
- scientific article; zbMATH DE number 1305490 (Why is no real title available?)
- Minkowski Addition of Polytopes: Computational Complexity and Applications to Gröbner Bases
- Approximate convex intersection detection with applications to width and Minkowski sums
- Convexity recognition of the union of polyhedra
- Robust MPC for linear systems with bounded disturbances based on admissible equilibria sets
- Differentially fixed ideals in affine semigroup rings
- Constrained polynomial zonotopes
- Nonlinear set‐membership state estimation based on the Koopman operator
- Minimal representations of tropical rational functions
- Nonlinear scalarization in set optimization based on the concept of null set
- Lineup polytopes of products of simplices
- Efficient geometric operations on convex polyhedra, with an application to reachability analysis of hybrid systems
- Complexity of approximating the vertex centroid of a polyhedron
This page was built for publication: On the hardness of computing intersection, union and Minkowski sum of polytopes
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q958243)
