Testing static equilibrium for legged robots

Consider a legged robot at fixed foot placements. Where can the robot move its center of mass (CM) while remaining in static equilibrium? If the terrain is flat, the CM must lie above the convex hull of the robot's feet. If the terrain is not flat, this often-used approximation can be arbitrarily bad. Instead, the CM must lie above the projection of a nonlinear convex set that is defined by the properties of each foot placement. This paper presents an algorithm to compute the shape of this projection and gives a tight bound on the algorithm's running time. It also presents a method of amortizing the cost of this computation when it is only necessary to test static equilibrium at particular CM positions--that is, when it is only necessary to test the membership of points in the projection of a convex set rather than find its shape.