9
$\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.
Improve this question
$\endgroup$
4
  • $\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
    Commented Jun 9, 2014 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
    Commented Jun 17, 2014 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
    Commented Jun 17, 2014 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
    Commented Jun 18, 2014 at 16:57

2 Answers 2

Reset to default
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.

Improve this answer
$\endgroup$
3
  • 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
    Commented Apr 10, 2014 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
    Commented Apr 10, 2014 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
    Commented Apr 10, 2014 at 19:02
1
$\begingroup$

The following algorithm may not be optimal, but should give a good approximation. We will use Simulated Annealing. Each configuration can be represented by the following parameters:

  1. Order of shapes from ground to top
  2. Rotation of each shape
  3. Horizontal displacement of each shape

To evaluate a configuration, we place shapes one at a time in the order given in 1 with the rotation from 2 and horizontal displacement from 3. Wait until the configuration settles into a stable position and then measure its height. A configuration can be "mutated" by changing one of the 3 attributes. Run standard Simulated Annealing procedure to find good configurations. To make this more efficient, we can limit the number of rotations in 2 to $k$ bins. Similarly we can limit the number of possible horizontal displacements. With the right parameters, each of the configurations in the original post can be achieved. For me the hardest part in implementing this is finding a good physics simulator that would allow realistic placement of these shapes.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.