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.


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

  • $\begingroup$ Ah, I understand now. Thank you Guilherme. I'll go back to the papers and spend a few hours working through the intuition again. $\endgroup$
    – Amir
    Nov 19, 2010 at 0:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.