Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

A previously posted question "mean minimum distance for N random points on a one-dimensional line" produced an elegant answer: for a line of length L, the expected minimum distance (between random points) = L/(N^2/1), or simply 1/(N^2-1) for a line of unit length.

I am wondering what the corresponding value would be for the unit plane? I am not a mathematician, but my intuition suggests the answer is simply 1/(N -1), given N points on a unit square (plane).

Am I correct?

share|improve this question
    
See also mathoverflow.net/questions/22592/…. –  Douglas Zare Mar 17 '13 at 16:11

4 Answers 4

Let $p_n(x)$ be the probability that $n$ points in the unit square are at distances at least $x$ from each other. The expected minimum distance $E_n$ is $\int_0^\sqrt{2} p_n(x)dx$. If we can estimate $p_n(x)$, we get estimates on the integral.

Here are two crude estimates for $p_n(x)$. If we have drawn $k$ points, the probability that the next is within $x$ of one of the points is at most $k \pi x^2$, and at least $k \frac{\pi}4 (\frac{x}2)^2 = k \pi x^2/16$. The latter comes from putting a disk of radius $x/2$ at each of the previous points. These disks can't overlap, and at least a quarter of each disk is inside the square. We could improve this significantly on a torus.

Lower bound:

$$\begin{eqnarray} p_n(x) & \ge & \prod_{k=0}^{n-1} \max(0,1-k\pi x^2) \newline &\ge &\prod_{k=0}^{n-1} \max(0,1-n\pi x^2)^{k/n} \newline & = & \max(0,1-n\pi x^2)^{(n-1)/2} \newline \int_0^\sqrt2 p_n(x)dx & \ge & \int_0^{1/\sqrt{n\pi}} (1-n\pi x^2)^{(n-1)/2 } dx. \end{eqnarray}$$

A trigonometric substitution works. Mathematica evaluates that integral as $$E_n \ge \frac{\Gamma((n+1)/2)}{n^{3/2} \Gamma(n/2)} = \frac{{n\choose n/2}\sqrt{\pi}} {2^n 2\sqrt{n}} \sim \frac{1}{n\sqrt{2}}.$$

Upper bound:

$$\begin{eqnarray}p_n(x) & \le & \prod_{k=0}^{n-1} \max(0,1-k\pi x^2/16) \newline & \le & \prod_{k=0}^{n-1} \max(0,1-\pi x^2/16)^k \newline & = & \max(0,1-\pi x^2/16)^{n(n-1)/2}\newline \int_0^\sqrt{2} p_n(x)dx &\le & \int_0^{4/\sqrt{\pi}}(1-\pi x^2/16)^{n(n-1)/2}dx. \end{eqnarray}$$

Mathematica evaluates that integral as $$E_n \le \frac{2 \Gamma(1 + n(n-1)/2)}{\Gamma(3/2 + n(n-1)/2)} = \frac{2 \sqrt{\pi}{t(n) \choose t(n)/2}}{2^{t(n)}} \sim \frac{2\sqrt{2}}{n}.$$

where $t(n) = n^2 -n + 1$.

So, these crude upper and lower bounds only differ by a factor of $4$, and for large $n$, $1/n$ might be about right.

share|improve this answer

The OP's intuition goes awry in the very first case, $N=2$, where it predicts an expected distance of 1. As I'll show below, the expected distance between two points in the unit square is less than 1, so whatever the actual answer is in general, it's not as simple as $1/(N-1)$.

The smartest way to show that the expected distance between two points is less than 1 is, I suppose, to explicitly compute it, calculating

$$\int_0^1\int_0^1\int_0^1\int_0^1 \sqrt{(x_1-x_2)^2 + (y_1-y_2)^2}dx_1dx_2dy_1dy_2.$$

The second smartest way, I imagine, would be to write a computer program that picks random points $P$ and $Q$ and keeps a running average of their distance apart until you feel confident in the approximation.

I decided to try the third (or maybe fourth or fifth or....) smartest way: Show that the expected distance is less than something that's less than 1, using the crudest upper bounds that work. I'll describe this in a somewhat prolix fashion, following my initial line of thought to a dead end, and then modifying it to get to the cheese. My real goal was to (dis)prove the result with as little hard work as possible, but I wound up spending an awful lot of time on it (mostly correcting mistakes).

To begin with, let's recast things from the "unit" square $[0,1]\times[0,1]$ to the "Unit" square, $[-1,1]\times[-1,1]$, which simply doubles the expected length. Calling the answer on the Unit square $E$, we now want to show that $E<2$.

It'll be helpful to draw the diamond connecting the midpoints of the sides of the Unit square, and refer to a point $(x,y)$ as being inner or outer depending on whether it's inside or outside the diamond, i.e. whether $|x|+|y|$ is less than or greater than 1. (You can assign the points with $|x|+|y|=1$ however you like, or ignore them altogether.)

Any two points are either in the Same quadrant, Adjacent quadrants, or polar Opposite quadrants, with probability $1/4$, $1/2$, and $1/4$ if the points are chosen at random. This gives

$$E = {1\over4}S + {1\over2}A + {1\over4}O,$$

where $S$, $A$, and $O$ are the expected distances in the three disjoint cases (ignoring the measure-0 overlaps). In each case, the two points will either both be inner, both be outer, or will be one of each, with corresponding probability $1/4$, $1/4$, and $1/2$. Let's look at the three cases in reverse order.

In case $O$, if the two points are both inner, the distance between them is at most 2. If they're both outer, the distance is at most $2\sqrt2$. And if they're one of each, the distance is at most $\sqrt5$. Hence

$$O \le {2\over4} + {2\sqrt2\over4} + {\sqrt5\over2}.$$

For case $A$, if the points are both inner, the distance between them is again at most 2, while if either one is outer, the distance is at most $\sqrt5$, so we have

$$A \le {2\over4} + {3\sqrt5\over4}.$$

Finally (modulo a refinement to come), in case $S$, the distance between two points, whether inner or outer, is at most $\sqrt2$, i.e.,

$$S \le \sqrt2.$$

Putting all this together gives

$$E \le {1\over4}(\sqrt2) + {1\over2}({2\over4} + {3\sqrt5\over4}) + {1\over4}({2\over4} + {2\sqrt2\over4} + {\sqrt5\over2})$$

The problem is, this simplifies to

$$E \le {3 + 3\sqrt2 + 4\sqrt5\over8} \approx 2.02336407,$$

which doesn't prove what we want. But there's a clever way out. That's to realize that case $S$ is simply the original problem, on the "unit" as opposed to "Unit" square. So instead of replacing $S$ with a crude upper bound, let's use

$$S={1\over2}E$$

and write

$$E = {1\over8}E + {1\over2}A + {1\over4}O,$$

which becomes

$$E = {4\over7}A + {2\over7}O.$$

This time, the crude upper bounds for $A$ and $O$ lead to

$$E \le {3+\sqrt2+4\sqrt5\over 7} \approx 1.90835507,$$

which is all we want.

If anyone can think of another way to show that $E<2$, please post it!

share|improve this answer
    
I asked Maple to evaluate your quadruple integral numerically. This uses the NAG procedure DCUHRE (TOMS algorithm 698). With the default settings it was unable to obtain the desired accuracy, but with relative error tolerance epsilon $= 10^{-4}$ the result was $.5214059909$. –  Robert Israel Mar 15 '13 at 19:19
    
@Robert, after spending a couple of hours coming up with an "easy" way to avoid doing the integral, I did the very easiest thing and googled on "average distance between two points in a square," which led to mathworld.wolfram.com/SquareLinePicking.html where the exact answer (which agrees numerically with what Maple gave you) is given. Note that doubling it from the unit square to the Unit square gives $E\approx 1.04281$. –  Barry Cipra Mar 15 '13 at 19:34
3  
If all you care about is showing that the expected distance is less than $1$ for $N=2$, I believe you can dodge most of the computation using by using Jensen's inequality to bound $[E(d)]^2≤E(d^2)=2E((x_1−x_2)^2)=\frac{1}{3}$. –  Kevin P. Costello Mar 15 '13 at 20:50
    
@Kevin, very nice! This gives an upper bound of 0.57735 for the unit square, or 1.1547 for the Unit square, which is a whole lot better than what I got. You should re-post it as a separate answer. –  Barry Cipra Mar 15 '13 at 22:06
    
By the way, Mathematica can simply do that integral. Timing[Integrate[Sqrt[(x1 - x2)^2 + (y1 - y2)^2], {x1, 0, 1}, {x2, 0, 1}, {y1, 0, 1}, {y2, 0, 1}]] {30.669, 1/15 (2 + Sqrt[2] + 5 ArcSinh[1])} –  Douglas Zare Mar 15 '13 at 23:19

This is a continuation to Douglas Zare's answer. I believe his lower bound of $1/n\sqrt{2}$ is the correct asymptotic behaviour. To see that, notice that all in inequalities in the calculation of the lower bound tend to equalities as $n\to \infty$, with the possible exception of the first inequality.

But in fact, the first inequality also tend to an equality when $n\to \infty$. This is because the error term is the measure of the overlap between discs of radius $x$ around the $k$ points and for $x=O(1/n)$, which is the relevant order of magnitude, this overlap is negligible - it's $O(k^2/n^4)$ whereas the measure of the discs is $\Theta(k/n^2)$.

share|improve this answer

Some empirical data, with each point the average of 50 trials:
           MinDistSquare
The curve $1/(\sqrt{2} n)$ (displayed) fits rather well. Congrats to Douglas Zare and Ori Gurel-Gurevich!

share|improve this answer
    
Very nice! although if we want asymptotic behaviour, we're only interested in the right side of the of the graph, where the curve is consistently below the data. –  Ori Gurel-Gurevich Mar 17 '13 at 5:48
1  
It looks like your estimate for $21$ was higher than for $19$. Why not generate the points in sequence, letting the examples for $n$ be prefixes of the examples for $n+1$? This would introduce some correlation, but it might be so much faster (depending on the algorithm) that it might be more efficient. I think the crude lower bound I calculated of about $1/(n \sqrt{2})$ is close to the actual value for large $n$ because it is rare to have a proportionally large overlap of small disks when each disk's center is outside the previous disks. Similarly, given the minimum distance for 19... –  Douglas Zare Mar 17 '13 at 6:32
    
... one should be able to approximate the distribution for the minimum distance when you add one more point quite well. –  Douglas Zare Mar 17 '13 at 6:33
    
I replaced the "best-fit" with $1/(\sqrt{2}n)$. Good idea, Douglas. For a later date... –  Joseph O'Rourke Mar 17 '13 at 13:11
    
I tried to extend your calculations. I split the square into $\sqrt{n} \times \sqrt{n}$ subsquares, and made a list of points in each subsquare and in the subsquares to the left, down, and left-and-down, so that every pair of points in adjacent subsquares would be on the same list, and the average length of a list would be $4$. Then I checked for the minimum distances between pairs of points on the same list. The expected time is linear in $n$. I get close agreement in $1000$ trials each with $n=10^3, 10^4, 10^5,$ and $10^6$. –  Douglas Zare Mar 21 '13 at 6:35

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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