Computing Immobilizing Grasps of Polygonal Parts

We present the first algorithms for computing all placements of (frictionless) point fingers that put a polygonal part in form closure and all placements of point fingers that achieve second-order immobility of a polygonal part. Our algorithms run in O(n 2+∈ +K) and O(n 2 log 2 n + K) time in the case of form closure and second-order immobility, respectively, where n is the number of vertices of the polygon, K is the description size of the resulting set of finger placements, and ∈ is an arbitrarily small constant. The basis of our algorithm is a translation of the problem into geometric searching problems, which are solved using efficient data structures. Our results can be extended to the problem of computing all placements of a line and two points that put a polygonal part in form closure. The resulting algorithm runs in O(n 2 log 2 n + K) time, where K is again the description size of the output.