Fast Implementation of Lemke's Algorithm for Rigid Body Contact Simulation

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(n³) to nearly O(nm + m³), 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.