Technical Reports

The ICICS/CS Reading Room

UBC CS TR-2005-01 Summary

Fast Implementation of Lemke's Algorithm for Rigid Body Contact Simulation, January 18, 2005 John E. Lloyd, 30 pages

We present a fast method for solving rigid body contact problems with friction, based on optimizations incorporated into Lemke's algorithm for solving linear complementarity problems. These optimizations reduce the expected solution complexity (in the number of contacts) from O(n3) to nearly O(n m + m3), where m is the number of bodies in the system. For a fixed m the expected complexity is then close to O(n). By simplifying internal computations our method also improves numerical robustness, and removes the need to explicitly compute the large matrices associated with rigid body contact problems.

If you have any questions or comments regarding this page please send mail to