부산대학교 도서관

We prove the following quantitative form of a classical theorem of Steintiz: Letmbe sufficiently large. If the convex hull of a subsetSof Euclideand-space contains a unit ball centered on the origin, then there is a subset ofSwith at mostmpoints whose convex hull contains a solid ball also centered on the origin and havingresidual radius % MathType!MTEF!2!1!+-% feaafiart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn% hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr% 4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrpepeei0xd9Wq-Jb9% vqaqFfpe0db9as0-LqLs-Jirpepeei0-bs0Fb9pgea0db9fr-xfr-x% frpeWZqaaeaabiGaciaacaqabeaadaqaaqaaaOqaaiaaigdacqGHsi% slcaaIZaGaamizamaabmaabaWaaSaaaeaacaaIYaGaamizamaaCaaa% leqabaGaaGOmaaaaaOqaaiaad2gaaaaacaGLOaGaayzkaaWaaWbaaS% qabeaacaaIYaGaai4laiaacIcacaWGKbGaeyOeI0IaaGymaiaacMca% aaGccaGGUaaaaa!4694! $$1 - 3d\left( {\frac{{2d^2 }}{m}} \right)^{2/(d - 1)} .$$ The casem=2dwas 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 % MathType!MTEF!2!1!+-% feaafiart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn% hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr% 4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrpepeei0xd9Wq-Jb9% vqaqFfpe0db9as0-LqLs-Jirpepeei0-bs0Fb9pgea0db9fr-xfr-x% frpeWZqaaeaabiGaciaacaqabeaadaqaaqaaaOqaaiaaigdacqGHsi% sldaWcaaqaaiaaigdaaeaacaaIXaGaaG4naaaadaqadaqaamaalaaa% baGaaGOmaiaadsgadaahaaWcbeqaaiaaikdaaaaakeaacaWGTbaaaa% GaayjkaiaawMcaamaaCaaaleqabaGaaGOmaiaac+cacaGGOaGaamiz% aiabgkHiTiaaigdacaGGPaaaaOGaaiOlaaaa!4735! $$1 - \frac{1}{{17}}\left( {\frac{{2d^2 }}{m}} \right)^{2/(d - 1)} .$$ These results have applications in the problem of computing the so-calledclosure graspsby anm-fingered robot hand. The above quantitative form of Steinitz's theorem gives a notion ofefficiencyfor 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.