Günter Rote and Uri Zwick:


In: Proceedings of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), San Francisco, January 2011, pp. 606–613.


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.

  pdf file (gzipped)
other papers about this subject
Last update: September 13, 2011.