zbMATH — the first resource for mathematics

Constructive approximation of a ball by polytopes. (English) Zbl 0799.52005
Let \(S_ n(r)\) denote the \(n\)-dimensional ball of radius \(r\) with centre at the origin. The author gives an explicit construction of \(m\) unit vectors \(v_ i \in S_ n(1)\) such that the convex hull \(\text{conv} \{v_ 1, \dots, v_ m\}\) contains a ball \(S_ n(r)\) with \(r=c \sqrt {n^{-1} \log (m/n)}\) for \(2n \leq m \leq k^ n\) with any constant \(k>1\). The constant \(c\) is independent on the dimension \(n\), and the value \(r\) is asymptotically optimal \((n \to \infty)\) but only for \(2n \leq m\). Contrary to the title the author does not consider the (best) approximating polytopes (with minimal number of vertices) of the ball in the sense of the minimal Hausdorff distance, for example.
Reviewer: E.Hertel (Jena)

52A27 Approximation by convex sets
52B55 Computational aspects related to convexity
52B12 Special polytopes (linear programming, centrally symmetric, etc.)
68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
Full Text: EuDML
[1] BÁRÁNY I., FÜREDI Z.: Computing the volume is difficult. Discrete Comput. Geom. 2 (1987), 319-326, and in: Proc. 18th Annual ACM Symposium on Theory of Computing, Berkeley, California, 1986, pp. 442-447. · Zbl 0628.68041
[2] BÁRÁNY I., FÜREDI Z.: Approximation of the sphere by polytopes having few vertrces. Proc. Amer. Math. Soc. 102 (1988), 651-659. · Zbl 0669.52003
[3] CARL B.: Inequalities of Berstein-Jackson-type and the degree of compactness of operators in Banach spaces. Ann. Inst. Fourier (Grenoble) 35 (1985), 79-118. · Zbl 0564.47009
[4] CARL B., PAJOR A.: Gelfand numbers of operators with values in Hilbert spaces. Invent. Math. 94 (1988), 479-504. · Zbl 0668.47014
[5] DANZER L., GRÜNBAUM B., KLEE V. : Helley’s theorem and its relatives. Convexity (V. L. Klee, Amer. Math. Soc., Providence, Rhode Island, 1963, pp. 101-180. · Zbl 0132.17401
[6] GOFFIN J. L. : Variable metric relaxation methods, Part II: The ellipsoid method. Math. Programming 30 (1984), 147-162. · Zbl 0567.90068
[7] GRÖTCHEL M., LOVÁSZ L., SCHRIJVER A.: Geometric Algorrthms and Combinatorial Optimization. Springer-Verlag, Berlin, 1988.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.