Design a site like this with
Get started

Approximation of a symmetric convex body by polytopes

Let K be an origin-symmetric symmetric convex body in \mathbb{R}^d, \varepsilon>0. What is the optimal upper bound for the number of vertices of the convex polytope L satisfying K\subset L\subset (1+\varepsilon)K? Here we may consider both large d and small \varepsilon. As far as I understand, in full generality the 2-parametric asymptotic is still open, see some recent results and a survey in the paper of Alexander Barvinok. UPDATE: Sasha Polyanskii immediately informed me about the result by Fedja Nazarov, Dima Ryabogin and Márton Naszódi where the sharp estimate is obtained.

Consider the fixed d regime. Recently I asked the participants of Online IMC 2020 to prove the O(\varepsilon^{1-d}) bound and I found out from the discussions after the contest that the sharp order is \varepsilon^{(1-d)/2}. The goal of this post is to share a nice argument for that borrowed from the paper by Bronstein and Ivanov (Siberian Math. Journal 1975), and a bit simplified. The lower bound is realised already for the Euclidean sphere, it is easy (each vertex a of L can see only O(\varepsilon^{(d-1)/2}) part of \partial K).

First of all, we make a linear transform so that the John ellipsoid of K is a unit ball B, now B\subset K\subset \sqrt{d}B.

K+\varepsilon B is contained in (1+\varepsilon)K and thus it suffices to find O(\varepsilon^{(1-d)/2}) points in K+\varepsilon B whose convex hull contains K. The idea is to use the parallel surface.

Namely, consider the boundary \Gamma of the set K+B and choose a minimal (by cardinality) \sqrt{\varepsilon}-net on \Gamma, denote it by T. We have |T|=O(\varepsilon^{(1-d)/2}) (since \Gamma is bi-Lipschitz equivalent to the surface of the unit cube, for example). For a\in T denote by n_a the outer normal to K+B at x (it is unique, but we do not use this), that is, such a unit vector that

\langle a,n_a\rangle=\max_{K+B} \langle \cdot,n_a\rangle= \max_{K} \langle \cdot,n_a\rangle +\max_{B} \langle \cdot,n_a\rangle=\max_{K} \langle \cdot,n_a\rangle+1.

It means that a=x_a+n_a, where n_a is an outer normal at x_a for the set K (there may exist other outer normals at x_a). The point f(a):=x_a+\varepsilon n_a belongs to K+\varepsilon B. Define L={\rm conv} \{f(a):a\in T\}. It suffices to prove that K\subset L if we assume \varepsilon<1/4. By convex duality, K\subset L is equivalent to

\max_L \langle \cdot,n\rangle \geqslant \max_K \langle \cdot,n\rangle\quad\quad (1)

for any unit vector n. For fixed n let x be a point on \partial K such that \langle x,n\rangle is maximal. We have x+n\in \Gamma, thus there exists a=x_a+n_a\in T such that

\varepsilon\geqslant |(x+n)-(x_a+n_a)||^2=\|x-x_a\|^2+\|n-n_a\|^2+2\langle x-x_a,n\rangle+2\langle x_a -x,n_a\rangle.

We have \langle x-x_a,n\rangle\geqslant 0 and \langle x_a-x,n_a\rangle\geqslant 0, thus

\varepsilon\geqslant \varepsilon+ 2\langle x_a-x,n\rangle \geqslant |n-n_a|^2 \geqslant 0,

in particular |n-n_a|\leqslant \sqrt{\varepsilon}<1/2 since \varepsilon<1/4. Thus for f(a)=x_a+\varepsilon n_a\in L we have

\langle f(a),n\rangle=\langle x_a+\varepsilon n_a,n\rangle=\langle x,n\rangle+\langle x_a-x,n\rangle +\varepsilon+\varepsilon\langle n_a-n,n\rangle \geqslant \langle x,n\rangle+\varepsilon/2+\varepsilon\langle n_a-n,n\rangle\geqslant \langle x,n\rangle

and (1) for n is proved.


Leave a comment

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: