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.

Cancel reply

Enter your comment here...

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

Email (required) (Address never made public)

Name (required)

Website

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

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

Cancel

Connecting to %s

Share this:

Like this:

Leave a comment

Cancel reply