  This article presents computationally efficient algorithms for modeling two
special cases of rigid contact---contact with only viscous friction and contact
without slip---that have particularly useful applications in robotic locomotion
and grasping. Modeling rigid contact with Coulomb friction generally exhibits
$O(n^3)$ expected time complexity in the number of contact points and
$2^{O(n)}$ worst-case complexity. The special cases we consider exhibit $O(m^3
+ m^2n)$ time complexity ($m$ is the number of independent coordinates in the
multi rigid body system) in the expected case and polynomial complexity in the
worst case; thus, asymptotic complexity is no longer driven by number of
contact points (which is conceivably limitless) but instead is more dependent
on the number of bodies in the system (which is often fixed). These special
cases also require considerably fewer constrained nonlinear optimization
variables thus yielding substantial improvements in running time. Finally,
these special cases also afford one other advantage: the nonlinear optimization
problems are numerically easier to solve.
