New answers tagged random-graphs
10
EDIT: Replaced the calculation for two dimensions by the case of arbitrary constant dimension. Added a table of the values.
I'd like to add an informal sketch of how David's very elegant result can be calculated. (To be clear, I suggest selecting his answer as the "correct" answer; this one is just intended to complement his.)
Assume the points are in ...
13
For $n$ uniformly random points in a unit square the number of components is
$$\frac{3\pi}{8\pi+3\sqrt{3}}n+o(n)$$
See Theorem 2 of D. Eppstein, M. S. Paterson, and F. F. Yao (1997), "On nearest-neighbor graphs", Disc. Comput. Geom. 17: 263–282, https://www.ics.uci.edu/~eppstein/pubs/EppPatYao-DCG-97.pdf
For points in any fixed higher dimension it is $\...
Top 50 recent answers are included
