Stacking Monotone Polytopes

Abstract

This paper addresses the problem of computing the optimal stacking of two monotone polytopes P and Q in Rd. A monotone polytope in Rd is defined as a polytope whose intersection with any line parallel to the last coordinate axis xd is connected, and the stacking of P and Q is defined as a translation of Q, such that “Q touches P from above”. To evaluate the stack, we use three different scoring criteria: (1) the height of the stack, (2) the maximum pointwise distance along the xd-axis, and (3) the volume between P and Q. We propose exact algorithms to compute the optimal stacking for each scoring criterion.

Keywords

• monotone polytope
• stacking problem
• exact algorithm
• computational geometry