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](https://arxiv.org/abs/1705.07754)", 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$.
> 
> 
> 



Existence of fine approximate of a convex body in $\mathbb R^d$ with convex hull of $\mathcal O(d)$ points
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](https://en.wikipedia.org/wiki/Spherical_cap#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](https://en.wikipedia.org/wiki/Spherical_cap#Hyperspherical_cap) 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$.


