QUANTITATIVE STEINITZ THEOREMS WITH APPLICATIONS TO MULTIFINGERED GRASPING

We prove the following quantitative form of a classical theorem of Steintiz: Let m be sufficiently large. If the convex hull of a subset S of Euclidean d-space contains a unit ball centered on the origin, then there is a subset of S with at most m points whose convex hull contains a solid ball also centered on the origin and having residual radius [GRAPHICS] The case m = 2d was first considered by Barany et al. [1]. We also show an upper bound on the achievable radius: the residual radius must be less than [GRAPHICS] These results have applications in the problem of computing the so-called closure grasps by an m-fingered robot hand. The above quantitative form of Steinitz's theorem gives a notion of efficiency for closure grasps. The theorem also gives rise to some new problems in computational geometry. We present some efficient algorithms for these problems, especially in the two-dimensional case.