On the exact maximum complexity of Minkowski sums of polytopes
type: Item
instance of: scholarly article
title: On the exact maximum complexity of Minkowski sums of polytopes
zbMATH Open document ID: 1207.52012
author: Efi Fogel
author: Dan Halperin
author: Christophe Weibel
published in: Discrete \& Computational Geometry
publication date: 2009-12-14T00:00:00Z
review text: It is shown that, if \(P_1, \dots, P_k\) are 3-dimensional convex polytopes lying in \(\mathbb R^3\) and if, for \(1\leq i \leq k\), \(m_i\) is the number of facets of \(P_i\), then the number of facets of the Minkowski sum \(P_1 + \cdots + P_k\) is at most \(4\sum_{1\leq i<j \leq k}m_im_j - (10k-11)\sum_{1\leq i \leq k} m_i + 26 {k\choose 2}\). Examples show that this bound can be achieved.
Mathematics Subject Classification ID: 52B10
Mathematics Subject Classification ID: 52B55
Mathematics Subject Classification ID: 68Q17
Mathematics Subject Classification ID: 68U05
zbMATH DE Number: 5646268
zbMATH Keywords: polyhedra
zbMATH Keywords: Minkowski sums
zbMATH Keywords: Gaussian maps
zbMATH Keywords: complexity
reviewed by: James F. Lawrence
MaRDI profile type: Publication
full work available at URL: s00454-009-9159-1
OpenAlex ID: W1979867394
cites work: Polygon decomposition for efficient construction of Minkowski sums
cites work: On Translational Motion Planning of a Convex Polyhedron in 3-Space
cites work: Q2779370
cites work: Exact and efficient construction of Minkowski sums of convex polyhedra with applications
cites work: From the zonotope construction to the Minkowski addition of convex polytopes
cites work: \(f\)-vectors of Minkowski additions of convex polytopes
cites work: Minkowski Addition of Polytopes: Computational Complexity and Applications to Gröbner Bases
cites work: A characterization of convex hyperbolic polyhedra and of convex polyhedra inscribed in the sphere
cites work: Maximal f-vectors of Minkowski sums of large numbers of polytopes
DOI: 10.1007/S00454-009-9159-1
description: scientific article; zbMATH DE number 5646268