Volume 27 Issue 11-12 - Publication Date: 1 November 2008
Caging Polygons with Two and Three Fingers
M. Vahedi and A. F. van der Stappen Department of Information and Computing Sciences, Utrecht University, 3508 TB Utrecht, The Netherlands
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 impossible 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 O(n2 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 O(n2 log n) time requiring O(n2) space that can be queried in O(log n) time whether a given two-finger grasp cages the polygon. We also establish a relation between two-finger caging grasps and two-finger immobilizing 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 reports the entire caging region in O(n6 log2 n) time. Our result extends a previous solution that only applies to convex polygons (Erickson et al. 2007).
Return to Contents