On sufficient numbers of fingers to immobilize 3d chains of polyhedra

We study the problem of bounding the number of fingers that suffice to immobilize a serial chain of n polyhedra (P 1 , . . . ., P n ), in which each pair of consecutive polyhedra P i+1 (for 1 ≤ i <; n) in the chain shares exactly one vertex ρ i . This vertex ρ i serves as a rotational joint, or hinge. We consider hinges ρ i with one degree of freedom, allowing for rotation of both incident subchains about a rotation axis ℓ i through ρ i , and with three degrees of freedom, allowing for free rotation of the incident subchains about ρ i itself. Besides immobility, we also study robust immobility [1] which additionally requires that sufficiently small perturbations of fingers along their respective facets do not destroy the immobility. Our paper provides the first bounds on the number offingers that suffice to immobilize three-dimensional articulated structures in any given configuration. The bounds are constructive in the sense that we point out how many fingers should be placed on each of the polyhedra in the chain. In the case of hinges with one degree of freedom, we show that 2 n+5 fingers suffice to immobilize a chain of arbitrary polyhedra robustly. If all polyhedra are convex and each axis ℓ i intersects the adjacent polyhedron P i+1 then only at most n+6 fingers suffice to immobilize the chain. In the case of hinges with three degree of freedom, we obtain bounds for arbitrary polyhedra and for irregular polyhedra, which satisfy the condition that the normals to any three different facets are linearly independent. We find that 4 n+5 fingers suffice to immobilize a chain of arbitrary polyhedra robustly. We also show that 3 n+1 fingers suffice to immobilize the chain if the polyhedra are irregular. If, in addition, all polyhedra are convex and no two hinges belong to a single facet of a polyhedron then only ⌊(5/2)n + 2⌋ fingers suffice.