Quantitative Steinitz's theorems with applications to multifingered grasping

David Kirkpatrick, Bhubaneswar Mishra, Chee Keng Yap

Research output: Contribution to journalArticle

Abstract

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 {Mathematical expression} The case m=2 d was first considered by Bárány et al. [1]. We also show an upper bound on the achievable radius: the residual radius must be less than {Mathematical expression} 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.

Original languageEnglish (US)
Pages (from-to)295-318
Number of pages24
JournalDiscrete & Computational Geometry
Volume7
Issue number1
DOIs
StatePublished - Dec 1992

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Geometry and Topology
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics

Fingerprint Dive into the research topics of 'Quantitative Steinitz's theorems with applications to multifingered grasping'. Together they form a unique fingerprint.

  • Cite this