On the exact maximum complexity of Minkowski sums of polytopes

DOI10.1007/S00454-009-9159-1zbMath1207.52012OpenAlexW1979867394MaRDI QIDQ1042457

Christophe Weibel, Efi Fogel, Dan Halperin

Publication date: 14 December 2009

Published in: Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00454-009-9159-1

zbMATH Keywords

complexitypolyhedraMinkowski sumsGaussian maps

Mathematics Subject Classification ID

Three-dimensional polytopes (52B10) Computational aspects related to convexity (52B55) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (6)

The maximum number of faces of the Minkowski sum of two convex polytopes ⋮ Maximal f-vectors of Minkowski sums of large numbers of polytopes ⋮ Unnamed Item ⋮ A counterexample to the Hirsch conjecture ⋮ A geometric approach for the upper bound theorem for Minkowski sums of convex polytopes ⋮ Solution methods for a min-max facility location problem with regional customers considering closest Euclidean distances

Cites Work

• Unnamed Item
• Maximal f-vectors of Minkowski sums of large numbers of polytopes
• Exact and efficient construction of Minkowski sums of convex polyhedra with applications
• \(f\)-vectors of Minkowski additions of convex polytopes
• From the zonotope construction to the Minkowski addition of convex polytopes
• A characterization of convex hyperbolic polyhedra and of convex polyhedra inscribed in the sphere
• On Translational Motion Planning of a Convex Polyhedron in 3-Space
• Minkowski Addition of Polytopes: Computational Complexity and Applications to Gröbner Bases
• Polygon decomposition for efficient construction of Minkowski sums

This page was built for publication: On the exact maximum complexity of Minkowski sums of polytopes