Günter Rote and Uri Zwick:
Collapse
In: Proceedings of the 22nd Annual ACM-SIAM Symposium on Discrete
Algorithms (SODA), San Francisco, January 2011, pp. 606–613.
Abstract
The problem of checking whether a given tower of bricks is stable can be
easily answered by checking whether a system of linear equations has a
feasible solution. A more challenging problem is to determine how an
unstable tower of bricks collapses. We use Gauß' principle of
least restraint to show that this, and more general rigid-body simulation
problems in which many parts touch each other, can be reduced to solving a
sequence of convex quadratic programs, with linear constraints, corresponding to
a discretization of time. The first of these quadratic programs gives an
exact description of initial infinitesimal collapse. The results of the
subsequent programs need to be integrated over time to yield an approximation
of the global motion of the system.
Last update: September 13, 2011.