Algorithms are given for constructing a polytope P with n vertices (facets), contained in (or containing) a given convex body K in ${ℝ}^d$, so that the ratio of the volumes |K∖P|/|K| (or |P∖K|/|K|) is smaller than $f\left(d\right)/n^{2/(d-1)}$.

The geometry of random projections of centrally symmetric convex bodies in ${ℝ}^N$ is studied. It is shown that if for such a body K the Euclidean ball $B{₂}^N$ is the ellipsoid of minimal volume containing it and a random n-dimensional projection $B=P_H\left(K\right)$ is “far” from $P_H\left(B{₂}^N\right)$ then the (random) body B is as “rigid” as its “distance” to $P_H\left(B{₂}^N\right)$ permits. The result holds for the full range of dimensions 1 ≤ n ≤ λN, for arbitrary λ ∈ (0,1).