$N$ points are generated randomly on the unit square, with a uniform distribution. What is the probability that they form a connected graph, given that two points are connected iff the distance between them is less than or equal to $d\in(0,\sqrt{2})$?

This should obviously be some function of $N$ and $d$.

  • 7
    $\begingroup$ Instead of a graph, one can think of this as generating discs of diameter $d$ with center in the unit square, and asking if the union forms a connected figure. Sounds difficult $\endgroup$ – leonbloy Sep 22 '11 at 21:05
  • $\begingroup$ These references are far from answering the question but might be of interest: ima.umn.edu/preprints/Jan83Dec83/34.pdf scipress.org/e-library/rpf/pdf/chap4/0197.PDF $\endgroup$ – leonbloy Sep 22 '11 at 21:10
  • $\begingroup$ I agree with leonbloy that this is likely to be a difficult question. I think it's a great one, though, and would love to know the answer, too. $\endgroup$ – Mike Spivey Sep 22 '11 at 23:12
  • 1
    $\begingroup$ @anon: The problem is that those random variables are not IID - for small $d$, if $p_1$ and $p_2$ are close enough to each other, then the probability that $p_n$ is 'close enough' to $p_2$ is highly correlated with the probability that it's 'close enough' to $p_1$. $\endgroup$ – Steven Stadnicki Sep 22 '11 at 23:29
  • 4
    $\begingroup$ Crossposted: mathoverflow.net/questions/76153/… $\endgroup$ – user940 Sep 23 '11 at 0:57

Let's brute force it. Start with code for Kruskal's algorithm, and then select a number of points (like 10), and find the maximal distance required by Kruskal over 10000 trials. With 10 points, 20 points, and 30 points, I got figures like the following:

maximal Kruskal distance on 10, 20, 30 points

Here's code for the 30 point image.

Histogram[Table[Max[With[{pts = RandomReal[{0,1},{30,2}]},

Looks like you could fit a distribution curve to those pretty easily. But that's beyond the duties of a brute forcer, so I'll stop there.


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.