2011/12/07 by Menelaos I. Karavelas, Karavelas, Menelaos I., Eleni Tzanaki +1
Computer Science · Mathematics · #52B05 (Primary) 52B11 #52C45 #68U05 (Secondary) #Advanced Combinatorial Mathematics #Combinatorics (math.CO) #Computational Geometry (cs.CG) #Computational Geometry and Mesh Generation #F.2.2 #FOS: Computer and information sciences #FOS: Mathematics #Point processes and geometric inequalities
paper · pdf · doi:10.48550/arxiv.1112.1535
openalex publication_date 2011/12/07 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Consider a set of r convex d-polytopes P1,P2,...,Pr, where d≥3 and r≥2, and let ni be the number of vertices of Pi, 1≤i≤r. It has been shown by Fukuda and Weibel that the number of k-faces of the Minkowski sum, P1+P2+...+Pr, is bounded from above by Φk+r(n1,n2,...,nr), where Φℓ(n1,n2,...,nr)= ∑_\substack1≤si≤ni s1+...+sr=ℓ ∏i=1r\binomnisi, ℓ≥r. Fukuda and Weibel have also shown that the upper bound mentioned above is tight for d≥4, 2≤r≤\lfloor(d)/(2)\rfloor, and for all 0≤k≤\lfloor(d)/(2)\rfloor-r. In this paper we construct a set of r neighborly d-polytopes P1,P2,...,Pr, where d≥3 and 2≤r≤d-1, for which the upper bound of Fukuda and Weibel is attained for all 0≤k≤\lfloor(d+r-1)/(2)\rfloor-r. Our approach is based on what is known as the Cayley trick for Minkowski sums. A direct consequence of our result is a tight asymptotic bound on the complexity of the Minkowski sum P1+P2+...+Pr, for any fixed dimension d and any 2≤r≤d-1, when the number of vertices of the polytopes is (asymptotically) the same.