Abstract
Consider a set of convex -polytopes , where and , and let be the number of vertices of , . It has been shown by Fukuda and Weibel that the number of -faces of the Minkowski sum, , is bounded from above by , where , . Fukuda and Weibel have also shown that the upper bound mentioned above is tight for , , and for all . In this paper we construct a set of neighborly -polytopes , where and , for which the upper bound of Fukuda and Weibel is attained for all . 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 , for any fixed dimension and any , when the number of vertices of the polytopes is (asymptotically) the same.
Connections
Explore this paper’s authors, topics and related work.
Building this map preview
BZPEER is loading the nearby papers, people, topics and institutions for this page.
Reviews 0
Write a review
No reviews yet.
Discussion 0
Add a comment
No comments yet.