Coverage of balls on random points in Euclidean space We have n points randomly distributed in a d-dimensional unit hypercube. We randomly sample k of those points and center a ball with radius r on each of those k points. Does there exist an estimate of the radius r such that r is the smallest radius expected to cover all the points with those k possibly overlapping balls?
 A: A partial answer:  You might as well pick the ball centers first (at random of course) and then wonder what happens after that.   If you want estimates rather than exact solutions, then there can't be much volume left most of the time, or else one of the other points has a good chance of landing outside of the balls.
In various regimes --- either high dimension $d$ or high ratio $n/k$, and possibly other cases --- I expect an instability to develop that makes $n$ not very irrelevant.  That is, I expect that for some $r$ that depends on $k$ and $d$, the balls usually cover the entire cube; while when $r$ is not all that much smaller, I expect that a significant volume is usually left over and a high chance that one of the remaining points lands in it.
I can't prove any of that, but it seems intuitive.  For instance it is supported by the fact that in high dimension $d$, the volume of a ball grows quickly with its radius.
This motivates looking at the simplified question of the expected covering radius of a random collection of points.  These slides by Alexander Reznikov look relevant to this question, particularly because he discusses the case of a cube.
In any case, even when a small amount of volume is usually left over for a given radius $r$, you can use the same sort of methods to estimate $r$ as you would use when no volume is usually left over.
A: Not an answer. But if anyone comes up with an analytic solution, they could
check that in dimension $d=3$, 
with $n=100$ points and a $k=10$ sample, the radius needed is about $r=0.66$.
Here are $n$ (blue) points and a $k$-sample (green) and one red point that is 
outside the balls centered on the green sample
points when $r=0.6$, i.e., too small to cover.
(There could well be other points uncovered, but I stopped
the computation when I found one.)

          


And here is an attempt to crudely depict the balls of radius $r=0.6$:

          


Increasing $r$ to $0.67$ in this particular example covers all points (and $r=0.66$ still leaves that one red point uncovered).

For $n=1000$ points and a $k=100$ sample, the radius needed is about $r=0.31$.
So the radius is definitely not constant with respect to the ratio $k/n$.
Added in response to a question from @DylanThurston.

          


          

Radius vs. the probability of covering all $n$ points.
$r$ at $0.01$ intervals.
Each point represents $100$ random trials.


A: In an email, Doug Jungreis gave me the following solution to this
question. His solution illustrates the case where $n=10^7$, $k=500$, and
$\epsilon = 1/100$.  It seems to work well in the datasets I'm looking at
(even where $d$ is small). I'm quoting his email directly instead of trying to reformat the notation and risk a mistake.
Doug makes two independence assumptions described by Greg Kuperberg:

The first independence assumption is that if $p$ is a typical point in
  the cube, then whether one ball covers it has little do with whether
  another ball covers it. Obviously this assumption is bad in when $d$ is
  small since points at the end are harder to reach than points in the
  middle. But easily by the time you get to 50 dimensions, almost
  everything is comparably in the middle.
The second independence assumption is that whether one point is
  covered has little to do with whether another point is covered. Again,
  this assumption is bad when $d$ is small, but it's a good assumption by
  the time you get to $d=50$ with the given parameters.

Here is Doug's solution:

Here is an estimate if $d$ is large.  I'll make the same independence
  assumptions as Greg.  If you choose 2 values $x,y$ in the unit interval,
  then their expected distance squared is $\int_0^1 \int_0^1 (x-y)^2 dx\, dy
= 1/6$, and their expected distance^4 is $\int_0^1 \int_0^1 (x-y)^4 dx\, dy
= 1/15$ (if I didn't make a mistake).  So the distance squared has mean
  1/6 and variance $1/15 - (1/6)^2 = 7/180$.  Then the distance squared
  between two points in the $d$-hypercube has mean $d/6$ and variance
  $7d/180$, and assuming $d$ is reasonably large, it is very close to
  normally distributed.  You want a 1/100 chance that any of the 10
  million points misses all 500 spheres, so a $1/10^9$ chance that a
  particular point misses all 500 spheres, so a $(1/10^9)^{1/500} =
.9594$ chance that a particular point misses a particular sphere.  So
  you want a .9594 chance that two particular points have distance^2
  greater than $r^2$.  The value .9594 corresponds to 1.744 standard
  deviations on a normal distribution, so $r^2$ should be roughly 1.744
  standard deviations below the mean, i.e., $r^2 = (d/6) - 1.744
\sqrt{7d/180}$.

