<p>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.</p>

CC BY-SA 2.5
2010-11-19T00:24:31.727Z
Ah, I understand now. Thank you Guilherme. I'll go back to the papers and spend a few hours working through the intuition again.
Amir
CC BY-SA 2.5
2010-11-18T20:31:49.587Z
2010-11-18T20:31:49.587Z
Guilherme D. da Fonseca
<p>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 :).</p>

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

<cg.comp-geom>
Approximating convex sets
Amir
# Approximating convex sets

(Asked by: username_0 on 2010-11-18)

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.

**Tags:** cg.comp-geom

---

## 1 answers

### Answer by username_1 on 2010-11-18. Score: 6 | Accepted answer

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.

> **Comments:**
> **username_0**: Ah, I understand now. Thank you Guilherme. I'll go back to the papers and spend a few hours working through the intuition again.  

---

