The maximum number of faces of the Minkowski sum of two convex polytopes

DOI10.1007/S00454-015-9726-6zbMATH Open1365.52013arXiv1106.6254OpenAlexW2221543170MaRDI QIDQ309640FDOQ309640

Authors: Menelaos I. Karavelas, Eleni Tzanaki 

Publication date: 7 September 2016

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

Abstract: We derive tight expressions for the maximum number of $k$-faces, $0lekled-1$, of the Minkowski sum, $P_{1}oplus{P}_2$, of two $d$-dimensional convex polytopes $P_1$ and $P_2$, as a function of the number of vertices of the polytopes. For even dimensions $dge2$, the maximum values are attained when $P_1$ and $P_2$ are cyclic $d$-polytopes with disjoint vertex sets. For odd dimensions $dge3$, the maximum values are attained when $P_1$ and $P_2$ are $lfloorfracd2floor$-neighborly $d$-polytopes, whose vertex sets are chosen appropriately from two distinct $d$-dimensional moment-like curves.

Full work available at URL: https://arxiv.org/abs/1106.6254

Recommendations

• The maximum number of faces of the Minkowski sum of two convex polytopes
• The maximum number of faces of the Minkowski sum of three convex polytopes
• The maximum number of faces of the Minkowski sum of three convex polytopes
• On the exact maximum complexity of Minkowski sums of polytopes
• A geometric approach for the upper bound theorem for Minkowski sums of convex polytopes

zbMATH Keywords

discrete geometryhigh-dimensional geometrycombinatorial geometryconvex polytopescombinatorial complexityMinkowski sum

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.) (52B05) (n)-dimensional polytopes (52B11) Combinatorial complexity of geometric structures (52C45)

Cites Work

• Algebraic Statistics for Computational Biology
• Title not available (Why is that?)
• Lectures on Polytopes
• Partially observable Markov decision processes: a geometric technique and analysis
• Title not available (Why is that?)
• The maximum numbers of faces of a convex polytope
• The Cayley trick, lifting subdivisions and the Bohne-Dress theorem on zonotopal tilings
• Topological obstructions for vertex numbers of Minkowski sums
• On the exact maximum complexity of Minkowski sums of polytopes
• A simple way to tell a simple polytope from its graph
• \(f\)-vectors of Minkowski additions of convex polytopes
• Title not available (Why is that?)
• The maximum number of faces of the Minkowski sum of two convex polytopes
• Maximal f-vectors of Minkowski sums of large numbers of polytopes
• Minkowski Addition of Polytopes: Computational Complexity and Applications to Gröbner Bases
• Title not available (Why is that?)
• Relative Stanley-Reisner theory and upper bound theorems for Minkowski sums
• The maximum number of faces of the Minkowski sum of three convex polytopes
• A geometric approach for the upper bound theorem for Minkowski sums of convex polytopes
• Convex hulls of spheres and convex hulls of convex polytopes lying on parallel hyperplanes
• Shellable Decompositions of Cells and Spheres.

Cited In (22)

• Cephoids: Minkowski sums of de Gua simplexes
• Title not available (Why is that?)
• Almost Simplicial Polytopes: The Lower and Upper Bound Theorems
• Log-concavity and lower bounds for arithmetic circuits
• A linear equation for Minkowski sums of polytopes relatively in general position
• Convexly independent subsets of Minkowski sums of convex polygons
• A geometric approach for the upper bound theorem for Minkowski sums of convex polytopes
• The maximum number of faces of the Minkowski sum of two convex polytopes
• The Minkowski sum of a simple polygon and a segment
• Maximal f-vectors of Minkowski sums of large numbers of polytopes
• Sharp Bounds for the Number of Regions of Maxout Networks and Vertices of Minkowski Sums
• Relative Stanley-Reisner theory and upper bound theorems for Minkowski sums
• A geometric approach for the upper bound theorem for Minkowski sums of convex polytopes
• Topological obstructions for vertex numbers of Minkowski sums
• On the exact maximum complexity of Minkowski sums of polytopes
• A worst-case optimal algorithm to compute the Minkowski sum of convex polytopes
• A tight lower bound for convexly independent subsets of the Minkowski sums of planar point sets
• The flag polynomial of the Minkowski sum of simplices
• \(f\)-vectors of Minkowski additions of convex polytopes
• The maximum number of faces of the Minkowski sum of three convex polytopes
• A worst-case optimal algorithm to compute the Minkowski sum of convex polytopes
• The maximum number of faces of the Minkowski sum of three convex polytopes

This page was built for publication: The maximum number of faces of the Minkowski sum of two convex polytopes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q309640)