Multimedia  

 

Volume 19 Issue 05 - Publications Date: 1 May 2000
 
Computing Immobilizing Grasps of Polygonal Parts
 
A.F. van der Stappen Department of Computer Science, Utrecht University, P.O. Box 80089, 3508 TB Utrecht, the Netherlands, C. Wentink and M.H. Overmars
 
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(n2 + EK) and O(n2 log2 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(n2 log2 n + K) time, where K is again the description size of the output.
 
Return to Contents