# Maximum Stacking Height Problem

Has the following problem been studied before? If yes, what approaches/algorithms were developed to solve it?

Problem ("Maximum Stacking Height Problem")

Given $n$ polygons, find their stable, non-overlapping arrangement that maximizes their stacking height on a fixed floor under the influence of gravity.

## Example

Three polygons: and three of their infinitely many stable, non-overlapping arrangements, with different stacking heights: ## Clarifications

• All polygons have uniform mass and equal density
• Friction is zero
• Gravity is acting on every point into the downwards direction (i.e. the force vectors are all parallel)
• A configuration is not considered stable if it rests on an unstable equilibrium point (for example, the green triangle in the pictures can not balance on any of its vertices, even if the mass to the left and the right of the balance point is equal)
• To further clarify the above point: A polygon is considered unstable ("toppling") unless it rests on at least one point strictly to the left and at least one point strictly to the right of its center of gravity (this definition greatly simplifies simulation and in particular makes position integration etc. unnecessary for the purpose of evaluating whether or not an arrangement is stable.
• The problem in its "physical" form is a continuous problem that can only be solved approximately for most cases. To obtain a discrete problem that can be tackled algorithmically, constrain both the polygon vertices and their placement in the arrangement to suitable lattices.

## Notes

• Brute force approaches of any kind are clearly infeasible. Even with strict constraints on the placement of polygons inside the lattice (such as providing a limited region "lattice space") the complexity simply explodes for more than a few polygons.
• Iterative algorithms must bring some very clever heuristics since it is easy to construct arrangements where removing any single polygon results in the configuration becoming unstable and such arrangements are unreachable by algorithms relying on every intermediate step being stable.
• Since the problem smells at least NP- but more likely EXPTIME-complete in the total number of vertices, even heuristics would be of considerable interest. One thing that gives hope is the fact that most humans will recognize that the third arrangement in the example is optimal.
• For that definition of "unstable" (though possibly not for more accurate ones), one can in principle solve the problem exactly by quantifier elimination of real closed fields. $\;$ – user12859 Jun 9 '14 at 19:39
• @RickyDemer: I'd really like to understand that but alas, although I did glance over the paper and follow the main points, I fail to see the connection. Could you give me a few more pointers? A link between the stacking problem and algebra certainly sounds intriguing. – user16652 Jun 17 '14 at 18:50
• That may be because I incorrectly linked to a decision procedure rather than a quantifier elimination algorithm. $\:$ This paper is a much better reference for what I was talking about. $\:$ I also found a paper about some quadratic cases that might suffice when the vertex coordinates are all rational. $\;\;\;\;$ – user12859 Jun 17 '14 at 20:12
• :) I also found some more material explicitly linking computational geometry to quantifier elimination. Now I understand what you meant by "though possibly not for more accurate ones"; indeed, it seems impossible to extend such purely formal methods to "real" physics, where complex constraints such as differential equations come into play. Nevertheless, thank you for the very interesting angle of attack, I shall spend some time studying it. – user16652 Jun 18 '14 at 16:57