1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ You may probably get an exact answer in one dimensions, if that interests you. For more dimensions, it should be possible to determine the exact asymptotic behavior (with respect to $N$), but I would not expect an exact answer. $\endgroup$ – Lord Soth Jun 28 '13 at 15:22
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thanks: your idea helped a bit. I tried a few other things in order to get a closed-form solution, but since I only needed these values to add to a graph (so it's not a formal demonstration of any kind), I decided to just run a few quick Monte Carlo simulations, and already got all that I need. Thanks once again for the quick reply! $\endgroup$ – Bruno Jun 28 '13 at 22:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.