On the hardness of computing intersection, union and Minkowski sum of polytopes
From MaRDI portal
Publication:958243
DOI10.1007/s00454-008-9097-3zbMath1155.52008OpenAlexW2000147742MaRDI QIDQ958243
Publication date: 2 December 2008
Published in: Discrete \& Computational Geometry (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00454-008-9097-3
Analysis of algorithms and problem complexity (68Q25) Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.) (52B05) (n)-dimensional polytopes (52B11) Linear programming (90C05)
Related Items
Constrained zonotopes: a new tool for set-based estimation and fault detection, Exact recursive updating of state uncertainty sets for linear SISO systems, Verification of Hybrid Systems, Economic model predictive control for robust optimal operation of sparse storage networks, 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, Unnamed Item, a-tint: a polymake extension for algorithmic tropical intersection theory, On highly robust efficient solutions to uncertain multiobjective linear programs, Self-duality of polytopes and its relations to vertex enumeration and graph isomorphism, Efficient geometric operations on convex polyhedra, with an application to reachability analysis of hybrid systems, Complexity of approximating the vertex centroid of a polyhedron, Set operations and order reductions for constrained zonotopes
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On the convex hull of the union of certain polyhedra
- Geometric algorithms and combinatorial optimization.
- On the Newton polytope of the resultant
- How good are convex hull algorithms?
- The Cayley trick, lifting subdivisions and the Bohne-Dress theorem on zonotopal tilings
- \(f\)-vectors of Minkowski additions of convex polytopes
- From the zonotope construction to the Minkowski addition of convex polytopes
- On the complexity of four polyhedral set containment problems
- Lectures on Polytopes
- Minkowski Addition of Polytopes: Computational Complexity and Applications to Gröbner Bases
- Generating all vertices of a polyhedron is hard
- Extended convex hull
