Expected minimum distance of a random point with respect a set of random points on the plane

Question

I need to estimate, or bound, the expected minimum distance of a random point with respect to a set of other random points, all of which are located inside of a bounded rectangle.

More specifically, let us suppose we randomly place $N$ points, $p_1, \ldots, p_n$, within a rectangle of sides $L_1$ and $L_2$. Let us also suppose we place another point, $X$, uniformly at random inside the same rectangle. Let $D$ be the minimum distance between $X$ and $p_1, \ldots, p_n$:

$D = min_{i=1\ldots,n} ||X - p_i||$

Is it possible to compute exactly, or to approximate, the expected value of $D$, as a function of the number of points $N$ and the dimensions of the rectangle?

If a more general answer is possible, for the case in which we place points in a $n$-dimensional bounded hypercube, instead of a rectangle, that would be great too. If not, suggestions regarding how to deal with the 2D case would already be of great help.

Any ideas on how to compute this are very welcome!

Thanks in advance,

Bruno

Answer 1

I don't know how to answer your question directly, because I think it's hard. You might get a useful value by going in reverse. Pick a fixed point $x$ in the rectangle, and $a>0$. Let $R$ denote the area of the rectangle, and $T$ denote the area within the rectangle of distance at most $a$ from $x$. Then $$Pr(D\ge a)=\left(\frac{R-T}{R}\right)^n$$ If you only want an approximation, I would recommend doing Monte Carlo on various values of $x$ (chosen uniformly at random) to get an aggregate value. If $a$ is small compared to the rectangle (i.e. $T$ is usually a disk) you don't even need Monte Carlo and can get an approximate analytical result.