Number of samples needed to get a given expected distance Suppose I have a surface in $\mathbb{R}^3$ with surface area $A$.
How many points do I need to (uniformly at random) sample so that the expected distance from each point to its nearest neighbor is $d$?
Dimensional analysis suggests the number of samples should be proportional to $\frac{A}{d^2}$. Can anything be said about the proportionality constant, if we don't know anything about the geometry of the surface?
 A: Suppose you pick $n$ points. Consider one of the chosen points, call it $x$. The probability that the distance to its nearest neighbour is less than $r$ is the probability that at least one other point lies within the disk of radius $r$ centered at $x$. Since the remaining $n-1$ points are drawn uniformly from the total area $A$, this probability is simply
$$P = 1 - \left(1-a(r)/A\right)^{n-1}$$
where $a(r)$ is the area of said disk. This is therefore the cumulative distribution function of the distance from $x$ to its nearest neighbour.
When $n$ is large, $P$ is approximately $1 - \exp(-na(r)/A)$. Now it's easier to consider $r$ as a function of $a$ instead, which we can do because $a$ increases monotonically with $r$. So the area of the smallest disk containing another point follows an exponential distribution with rate $\lambda = n/A$, because its cumulative distribution function is
$$F(a) = P = 1 - \exp(-\lambda a).$$
Then the expected value of $r$ can be expressed as
$$\bar r = \int r(a) F'(a)\,\mathrm da = \int r(a)\lambda\exp(-\lambda a)\,\mathrm da.$$
Large values of $a$, i.e. those much greater than $\lambda^{-1} = A/n$, occur with exponentially small probability and can be neglected. So if a disk of area $A/n$ is very small relative to the curvature of the surface, one may approximate $a \approx \pi r^2$, so $r(a) \approx \sqrt{a/\pi}$, and obtain
$$\bar r \approx \frac12\sqrt{\frac An}.$$
