Abstract
We prove the following quantitative form of a classical theorem of Steintiz: Letm be sufficiently large. If the convex hull of a subsetS of Euclideand-space contains a unit ball centered on the origin, then there is a subset ofS with at mostm points whose convex hull contains a solid ball also centered on the origin and havingresidual radius
The casem=2d was first considered by Bárányet al. [1]. We also show an upper bound on the achievable radius: the residual radius must be less than
These results have applications in the problem of computing the so-calledclosure grasps by anm-fingered robot hand. The above quantitative form of Steinitz's theorem gives a notion ofefficiency 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.
Article PDF
Similar content being viewed by others
References
I. Bárány, M. Katchalski, and J. Pach. Quantitative Helly-type theorems.Proc. Amer. Math. Soc., 86:109–114, 1982.
C. Carathéodory. Über den Variabilitätsbereich der Koeffizienten von Potenzreihen, die gegebene Werte nicht annehmen.Math. Ann., 64:95–115, 1907.
V. Chvátal.Linear Programming. Freeman, New York, 1983.
K. L. Clarkson. Linear programming in\(O(n3^{d^2 } )\) time.Inform. Process. Lett., 22:22–24, 1988.
M. E. Dyer. On a multidimensional search technique and its application to the Euclidean one center problem. Technical Report, Teeside Polytechnic, England, 1984.
I. S. Gradshteyn and I. M. Ryzhik.Table of Integrals, Series and Products. Corrected and enlarged edition. Academic Press, New York, 1980.
N. Megiddo. Linear programming in linear time when the dimension is fixed.J. Assoc. Comput. Mach., 31(1):114–127, 1984.
B. Mishra. Our exagmination of work in progress: tele and dextrous manipulation. Technical Report 194, Robotics Research Lab., Courant Institute of Mathematical Sciences, New York University, March 1989.
B. Mishra. Dexterous manipulation: a geometric approach.Proceedings of the Second International Workshop on Advances in Robot Kinematics, Linz, Austria, September 1990.
B. Mishra and N. Silver. Some discussion of static gripping and its stability.IEEE Trans. Systems Man Cybernet., 19:783–796, July/August 1989.
B. Mishra, J. T. Schwartz, and M. Sharir. On the existence and synthesis of multifinger positive grips.Algorithmica, 2:541–558, 1987.
J. Pertin-Troccaz. Grasping: a state of the art. In O. Khatib, J. J. Craig, and T. Lozano-Perez, editors,The Robotics Review 1. MIT Press, Cambridge, MA, 1989, pp. 71–98.
E. Steinitz. Bedingt Konvergente Reihen und Konvexe Systeme i.J. Reine Angew. Math., 144:128–175, 1913.
E. Steinitz. Bedingt Konvergente Reihen und Konvex Systeme ii.J. Reine Angew. Math., 144:1–40, 1914.
E. Steinitz. Bedingt Konvergente Reihen und Konvexe Systeme iii.J. Reine Angew. Math., 146:1–52, 1916.
C. Yap. A geometric consistency theorem for a symbolic perturbation scheme.J. Comput. System Sci., 40(1):2–18, 1990.
Author information
Authors and Affiliations
Additional information
This research was supported by NSF Grants DCR-84-01898, DCR-84-01633, ONR Grant N00014-89-J3042, and NSF Grant Subcontract CMU-406349-55586. Chee-Keng Yap was supported in part by the German Research Foundation (DFG) and by the ESPRIT II Basic Research Actions Program of the EC under Contract No. 3075 (project ALCOM).
Rights and permissions
About this article
Cite this article
Kirkpatrick, D., Mishra, B. & Yap, CK. Quantitative Steinitz's theorems with applications to multifingered grasping. Discrete Comput Geom 7, 295–318 (1992). https://doi.org/10.1007/BF02187843
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/BF02187843