Using Probability to Cover a Geometric Set

Notes from book “High Dimensional Probability” - Using Probability to Cover a Geometric Set

Caratheodory’s theorem

Every point in the convex hull of a set $T \subset \mathbb{R}^n$ can be expressed as a convex combination of at most $n + 1$ points from $T$.

However if we approximate the point $x \in \text{conv}(T)$, the number of required points does not need to depend on the dimension $n$.

Approximate form of Caratheodory’s theorem

Consider a set $T \subset \mathbb{R}^n$ whose diameter is bounded by 1. Then, for every point $x \in \text{conv}(T)$ and every integer $k$, one can find the points $x_1, \cdots, x_k \in T$ such that

\begin{equation} \left\lVert x - \frac{1}{k} \sum_{j = 1}^{k} x_j \right\rVert_2 \leq \frac{1}{\sqrt{k}}. \end{equation}

Covering Polytopes by balls

Let $P$ be a polytope in $\mathbb{R}^n$ with $N$ vertices and whose diameter is bounded by 1. Then $P$ can be covered by at most $N^{\lceil 1/\epsilon^2 \rceil}$ Euclidean balls of radii $\epsilon > 0$