Efficient Algorithms for Stacking Polytopes

Abstract

Stacking objects is a common task in various industries. For example, finding a way to efficiently stack items in logistic could lead to economic benefit by reducing the storage space for them. Also in construction, it is crucial to stack logs in a way that they do not fall down. In this thesis, we consider a problem of stacking two objects P and Q, where the objects are given as x_d-monotone polytopes in R^d. We are allowed to translate Q while P is stationary. The goal is finding an optimal translation of Q to place Q on top of P. We present three criteria to determine the optimal translation, and give each algorithm to find the optimal translation. We reduce the objects into contacting surfaces P_c and Q_c, where P_c is the upper boundary of P and Q_c is the lower boundary of Q.