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.
and three of their infinitely many stable, non-overlapping arrangements, with different stacking heights:
- 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.
- 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.