On the complexity of the set of three-finger caging grasps of convex polygons

We study three-finger caging grasps of convex polygons. A part is caged with a number of fingers when it is impossible to rigidly move the part to an arbitrary placement far from its initial placement without penetrating any finger. A convex polygon with vertices and a placement of two fingers -referred to as the base fingers-are given. The caging region is the set of all placements of the third finger that together with the base fingers cage the polygon. We derive a novel formulation of caging in terms of visibility in three-dimensional space. We use this formulation to prove that the worst-case combinatorial complexity of the caging region is close to ( 3 ), which is a significant improvement of the previously known upper bound of ( 6 ). Moreover we provide an algorithm with a running time close to ( 3 log ) that considerably improves the current best known algorithm, which runs in ( 6 ) time.