# Hidden constant in eps-sample size computation

Given a range space $(X,R)$ with VC-Dimension $\le d$, we can create an $\varepsilon$-sample with probability at least $1-\delta$ by sampling $O\left(\frac{1}{\varepsilon^2}\left(d+\log\frac{1}{\delta}\right)\right)$ points with replacement from $X$.

Löffler and Phillips [1] showed experimentally that the constant hidden in the Big-Oh notation is at most 0.5. I was wondering whether there is any known theoretical, rather than experimental, upper bound to this constant.

Thanks in advance for any reference

[1] Löffler, M and Phillips, J.M. "Shape fitting on point sets with probability distributions". ESA'09

• By "one-dimensional case for sampling" I meant that this work referred to random sampling bounds. There are other deterministic approaches. In one dimension, sorting and taking $1/\epsilon$ evenly spaced points will yield an $\epsilon$-sample deterministically. Here the constant is 1, and the dependence on $\epsilon$ is much better. More complicated results exist for other range spaces as well, but the constants are much less understood, and likely much worse. – Jeff Phillips Nov 9 '12 at 7:35