8
$\begingroup$

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:

enter image description here

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

enter image description here


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.
$\endgroup$
  • $\begingroup$ 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. $\;$ $\endgroup$ – user12859 Jun 9 '14 at 19:39
  • $\begingroup$ @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. $\endgroup$ – user16652 Jun 17 '14 at 18:50
  • 1
    $\begingroup$ 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. $\;\;\;\;$ $\endgroup$ – user12859 Jun 17 '14 at 20:12
  • $\begingroup$ :) 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. $\endgroup$ – user16652 Jun 18 '14 at 16:57
1
$\begingroup$

While I don't know of any specific algorithms for this problem, you could approach this in a pretty efficient method by breaking it down into separate parts.

I would start by finding the rotation for each individual shape that provides a maximum height while maintaining a valid balancing orientation (is: not on a point like with the triangle). If a shape has multiple equal heights, i would go with the configuration that gives the greatest surface area on top of it. Once you have this, you can then figure out how to best stack each object in a manor that is able to be balanced.

$\endgroup$
  • 4
    $\begingroup$ It's pretty easy to construct examples where this approach leads to a suboptimal solution. For instance, consider a parallelogram obtained by shearing a very long rectangle (to make it only stable if it rests on its long side) plus a triangle matching its shearing angle. Individually, with your approach you'd be forced to turn the parallelogram so that it rests on its long side, but the triangle can support it to make it "stand up" (note that the zero-friction problem can easily be overcome by adding a small nook to the parallelogram that allows the triangle to "hook in"). $\endgroup$ – user16652 Apr 10 '14 at 18:29
  • $\begingroup$ That is true, I hadn't thought about that. One solution to that could be to check for shapes that can be used as support for the object, but that might not always provide an optimal height. You could try that still though and check against multiple total configurations for the best height, as that should still be better than a brute force. $\endgroup$ – GEMISIS Apr 10 '14 at 18:36
  • $\begingroup$ Here also one runs into significant problems, namely when it is not one object that supports another, but a stack of objects having just the right height to support a very large object standing up. The algorithms to check all that get arbitrarily complex. That being said, I do agree that it should be possible to obtain "better than brute force" runtime with some sensible eliminations. $\endgroup$ – user16652 Apr 10 '14 at 19:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy