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

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

2011-06-30

arxiv.org/abs/1106.6254v2

Computer Science

Computational Geometry

37 pages, 8 figures, conference version to appear at SODA 2012; v2: fixed typos, made stylistic changes, added figures

Scientific paper

We derive tight expressions for the maximum number of $k$-faces, $0\le{}k\le{}d-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 $d\ge{}2$, the maximum values are attained when $P_1$ and $P_2$ are cyclic $d$-polytopes with disjoint vertex sets. For odd dimensions $d\ge{}3$, the maximum values are attained when $P_1$ and $P_2$ are $\lfloor\frac{d}{2}\rfloor$-neighborly $d$-polytopes, whose vertex sets are chosen appropriately from two distinct $d$-dimensional moment-like curves.

Affiliated with

Also associated with

No associations

Rating

The maximum number of faces of the Minkowski sum of two convex polytopes does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with The maximum number of faces of the Minkowski sum of two convex polytopes, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The maximum number of faces of the Minkowski sum of two convex polytopes will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-35377