Return to 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$.

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$.

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$.

Let $K$ be a convex body in $\mathbb R^d$ and let $\theta \in (0,\infty)$.

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$.

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$.

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$.

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$.

Let $K$ be a convex body in $\mathbb R^d$ and let $\theta \in (0,\infty)$.

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$.

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=_{\theta} \mathcal O(\exp(d))$ 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$.

Let $K$ be a convex body in $\mathbb R^d$ and let $\theta \in (0,\infty)$.

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$.

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$.