Existence of fine approximate of a convex body in $\mathbb R^d$ with convex hull of $\mathcal O(d)$ points

Question

Let $K$ be a convex body in $\mathbb R^d$ which contains the origin and let $\theta \in (0,1)$.

Question. Is it always possible to find $n$ points $x_1,\dotsc,x_n \in \mathbb R^d$ such that $$ \theta K \subseteq \operatorname{conv}\{x_1,\dotsc,x_n\} \subseteq K \tag{1}\label{1} $$ and $n \le C_\theta d$ for some constant $C_\theta < \infty$ which only depends on $\theta$?

I'm interested in the case where $\theta \to 1$.

Note. I don't care about constructive / algorithmic solutions. I'm only interested in existence.

Some known results:

• From Theorem 1.1 of "Approximating a convex body by a polytope using the epsilon-net theorem", we know that if $\theta=1/d$, then $n = 500d$ points drawn uniformly at random of from $K$ satisfy \eqref{1} with probability $1-e^{-d}$. The issue with this result is that it only works for $\theta \ll 1$.

• From Theorem 1.2 of the same paper, we know that if $n= \mathcal O(dc_\theta^d)$ (with $c_\theta := 1 / (1 - \theta)>1$) points are drawn uniformly at random from $K$, then \eqref{1} is satisfied with probability $1-e^{-d}$. The issue with this result is that the dependence of $n$ on $d$ is exponential. We need linear.

On second thought it seems the bounds implied by the above results are an artifact of the complete randomness in the points $x_1,\dotsc,x_n$.

Answer 1

This is false for any fixed $\theta\in(\frac{1}{2},1)$, we will use the balls of radius $1$ in $\mathbb{R}^d$ as a counterexample. Given $\theta$, if we want $ \theta K \subseteq \operatorname{conv}\{x_1,\dotsc,x_n\} \subseteq K $, we will need at least one of the $x_i$ to be in the convex closure of each hyperspherical cap of height $1-\theta$. This implies each point of the sphere needs to have some $x_i$ at distance $<\sqrt{2(1-\theta)}$ from it (that´s the radius of the hyperspherical cap of height $1-\theta$). Call $R=\sqrt{2(1-\theta)}$, so that $R<1$ if $\theta>\frac{1}{2}$.

Then, the union of the $n$ balls $B_i$ of radius $R<1$ and centers the points $x_i$ has to cover the sphere. But each $B_i$ will cover a spherical cap of the sphere with height $\leq h$, for some $h<1$ (concretely, $h=1-\sqrt{1-R}$). So, calling $V_n$ the $n^{th}$ dimensional volume and $C^n_h$ the hyperspherical cap of $S^n$ and height $h$, we just have to prove that $\frac{V_{n}(S^n)}{V_n(C^n_h)}$ grows more than linearly for any $h<1$.

To do that we just use the volume formulas here and we have $$\frac{V_{n}(S^n)}{V_n(C^n_h)}=\frac{\int_0^\pi \sin^n(t)dt}{\int_0^{\arccos(1-h)}\sin^n(t)dt}.$$

In this quotient, the term below decreases exponentially, as $\sin(t)$ is bounded in $[0,\arccos(1-h)]$ by some constant $<1$. But the term above decreases very slowly, as it is in fact $\frac{\sqrt{\pi}\cdot\Gamma\left(\frac{n+1}{2}\right)}{\Gamma\left(1+\frac{n}{2}\right)}$, which decreases more or less like $\frac{1}{\sqrt{n}}$.

This means that the quotient above increases exponentially, so you´ll need $n$ to grow at least exponencially on $d$.