Caging Polygons with Two and Three Fingers

We study two- and three-finger caging grasps of a given polygonal object with n edges. A grasp is said to cage an object when it is im-possible to take the object to a distant location without penetrating a finger. Using a classification into squeezing and stretching cagings, we provide an algorithm that reports all caging grasps of two disk fingers in On2 log n time. Our result extends and improves a recent solution for point fingers (Pipattanasomporn and Sudsang 2006). In addition, we construct a data structure in On2 log n time requir-ing On2 space that can be queried in Olog n time whether a given two-finger grasp cages the polygon. We also establish a re-lation between two-finger caging grasps and two-finger immobiliz-ing grasps of polygons without parallel edges. We also study caging grasps with three point fingers. Given the placements of two so-called base fingers, the caging region is the set of all placements of the third finger that jointly with the base fingers forms a caging grasp of a polygonal object. Using the relation between equilibrium grasps and the boundary of the caging region, we present an algorithm that re-ports the entire caging region in On6 log2 n time. Our result extends a previous solution that only applies to convex polygons (Erickson et al. 2007). KEY WORDS—Robotic manipulation, caging grasps, planer parts, geometric data structures 1