Computing all immobilizing grasps of a simple polygon with few contacts

We study the output-sensitive computation of all the combinations of edges and concave vertices of a simple polygon that allow an immobilizing grasp with less than four frictionless point contacts. More specifically, if n is the number of edges, and m is the number of concave vertices of the polygon, we show how to compute: in O(m4/3 log1/3 m + K) time, all K combinations that allow a form-closure grasp with two contacts; in O(n2 log4 m + K) time, all K combinations that allow a form-closure grasp with three contacts; in O(n log4 m + (nm)2/3 log2+e m + K) time (for any constant e > 0), all K combinations of one concave vertex and one edge that allow a grasp with one contact on the vertex and one contact on the interior of the edge, satisfying Czyzowicz's weaker conditions for immobilization; in O(n2 log3 n + K) time, all K combinations of three edges that allow a grasp with one contact on the interior of each edge, satisfying Czyzowicz's weaker conditions for immobilization.