Output-Sensitive Computation of Force-Closure Grasps of a Semi-Algebraic Object

We propose a technique which significantly simplifies the computation of frictionless force-closure grasps of a curved planar part P. We use a colored projection scheme from the three-dimensional wrench space to two-dimensional screens, which allows us to reduce the problem of identifying combinations of arcs and concave vertices of P that admit frictionless force-closure grasps, to colored intersection searching problems in the screens. We show how to combine this technique with existing intersection searching algorithms to obtain efficient, output-sensitive algorithms to compute all force-closure grasps of P, where at most four hard, frictionless point contacts exert exactly four wrenches on P. If the boundary of P consists of n algebraic arcs of constant complexity and m concave vertices, we show how to compute all force-closure grasps with: (1) four contacts along four arcs in O(n^8/3log^1/3n+K) time; (2) four contacts along three arcs in O(n^5/2+ε + K) time; (3) one contact at a concave vertex and two contacts along two arcs in O(n²m^1/2+ε + K) time; (4) one contact at a concave vertex and two contacts along a single arc in O(nm) or O(n^3/2+ε + K) time (depending on the size of m); where ε is an arbitrarily small positive constant and K is the output size-that is, the number of combinations of arcs and vertices of each type, that actually admit frictionless force-closure grasps.