Approximating convex sets

Question

In the Haussdorf approximation of a convex object $C$ (and in much core-set work), the standard approach is to take an $\epsilon$-net on the enclosing hyper-sphere, then project it down to $C*(1 + \epsilon)$, where $C*(1+ \epsilon)$ is defined as $C$ projected outwards normally by an $\epsilon$ factor. I have a basic understanding of the proofs, but I'm trying to visualize why the hypersphere is really necessary. If you take an $\epsilon$-net on the surface of $C*(1+\epsilon)$ itself, would that not suffice? If there is an immediately obvious reason it would not work, I'd appreciate the clarification :).

Note: The $\epsilon$-net here is defined as a collection of equally spaced points on given surface.

Answer 1

The construction you suggest does work, but it is not optimal. The reason why people use the sphere with a constant expansion is that then a $\sqrt{\epsilon}$-net is enough. That reduces the size of the coreset from $O(1/\epsilon^{d-1})$ to $O(1/\epsilon^{(d-1)/2})$. To see that replacing $\epsilon$ by $\sqrt{\epsilon}$ in your construction does not work, consider the case of a regular triangle (or simplex) where only points within distance roughly $\sqrt{\epsilon}$ of the vertices are sampled.