Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

$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$.

share|improve this question
7  
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 –  leonbloy Sep 22 '11 at 21:05
    
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 –  leonbloy Sep 22 '11 at 21:10
    
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. –  Mike Spivey Sep 22 '11 at 23:12
1  
@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$. –  Steven Stadnicki Sep 22 '11 at 23:29
4  
Crossposted: mathoverflow.net/questions/76153/… –  Byron Schmuland Sep 23 '11 at 0:57
show 4 more comments

1 Answer 1

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}]},
EuclideanDistance[pts[[#]][[1]],pts[[#]][[2]]]&/@List@@@Kruskal[pts]]],{10000}]]

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.

share|improve this answer
add comment

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.