Science Forums

# Mean nearest neighbor distance in 3d

## Recommended Posts

Hi. In 3 dimensional Euclidean space with the usual metric, d=[(delta x)^2+(delta y)^2+(delta z)^2]^1/2, I'm trying to figure out the average distance between nearest neighbors in a randomly distributed sample of particles. My best initial guess for the average distance from any given particle to its nearest neighbor is d_nearest neighbor_mean=(volume/n)^1/3 where n particles are randomly distributed in a 3 dimensional volume.

The question originated when I wondered what was the average distance between stars in the solar neighborhood. atlasoftheuniverse.com gives 35 stars (including the Sun) within 12.5 light-years, and the above formula yields 6.16 ly as the avg distance from any given star to its closest neighbor. This seemed a little high to me, since the distance from the Sun to its nearest neighbor (Proxima Centauri) is 4.4 ly. But perhaps the Sun has a closer-than-avg nearest neighbor, since, after all, the distribution should be very close to random. Let us assume that the stars are randomly distributed.

I originally thought it would be easy to figure this out, but after trying unsuccessfully for an hour to work out a better formula, then another hour trying to google one, I gave up. Thanks in advance :(

##### Share on other sites
Hi. In 3 dimensional Euclidean space with the usual metric, d=[(delta x)^2+(delta y)^2+(delta z)^2]^1/2, I'm trying to figure out the average distance between nearest neighbors in a randomly distributed sample of particles. My best initial guess for the average distance from any given particle to its nearest neighbor is d_nearest neighbor_mean=(volume/n)^1/3 where n particles are randomly distributed in a 3 dimensional volume.

The mean random distance is smaller than the mean uniform distance (which is what you find with (v/n)^1/3) in two dimensions. You can see here:

toward the end. I don't know the formula for 3D, but in 2D the expected mean random distance to the nearest neighbor is given by:

$\overline{r}(e) = \frac{.5}{\sqrt{\rho}}$

where $\rho$ is the density (n/area). This does not generalize into 3D as one might intuitively think:

$\overline{r}(e) = \frac{.5}{\rho^{1/3}}$

The above is not correct.

Someone more practiced in their math skills might be able to look at the 2D derivation and give you a solution in 3D... :shrug:

Here's a different derivation:

Probability, statistical optics, and ... - Google Books

~modest

##### Share on other sites

Modest at

http://hypography.com/forums/physics-mathematics/21509-mean-nearest-neighbor-distance-3d.html

Probability, statistical optics, and ... - Google Books

And now I need to integrate:

integral of x^3 exp(-a x^3) dx, with a = constant,

but I couldn't. Hopefully, it's an easy integral and and someone will figure it out.

In a 3-dimensional random distribution, the basic idea for finding the average distance from any given particle to its nearest neighbor begins with:

P®dr = [1 - integral from 0 to r of P®dr][4 pi r^2 pho dr] (1)

where

pho = average number of particles/unit volume

P® dr = the probability of a particle's nearest neighbor occurring in the interval [r,r+dr]

integral from 0 to r of P® dr = probablity that an arbitrary particle's nearest neighbor lies within a distance r of the particle

1 - integral from 0 to r of P® dr = the probability that the nearest neighbor is no closer than r.

differentiating & separating eq. 1:

dP/P = [2/r - 4 pi rho r^2] dr

integrating:

P = [constant] r^2 exp(- [4/3] pi rho r^3)

normalizing:

1 = integral from 0 to infinity of P® dr

1 = [constant] integral from 0 to infinity of r^2 exp(-[4/3] pi rho r^3) dr

1 = [constant] [-[1/(4 pi rho)] exp(-[4/3] pi rho r^3)] evlauated from 0 to infinity

gives the constant = 4 pi rho and P® = 4 pi rho r^2 exp(-[4/3] pi rho r^3)

The average distance from any given particle to its nearest neighbor in 3 dimensions is then the expectation value of r:

<r> = integral from 0 to infinity of r P® dr

<r> = [4 pi rho] [integral from 0 to infinity of r^3 exp(-[4/3] pi rho r^3) dr]

I was unable to do the last integral, but I'm sure someone can :)

##### Share on other sites
<r> = integral from 0 to infinity of r P® dr

<r> = [4 pi rho] [integral from 0 to infinity of r^3 exp(-[4/3] pi rho r^3) dr]

I was unable to do the last integral, but I'm sure someone can :)

I'm quite sure I can't, but evaluating it numerically should at least confirm your work. The function,

$f®=r^3 e^{\left( -4/3 \pi \rho r^3 \right)}$

where $\rho$ = 0.004278 ly-3 very quickly approaches zero at r > 10. Thus,

$A = \int_0^{100} r^3 e^{\left( -4/3 \pi \rho r^3 \right)} \,dr = 63.476778$

and,

$r = 4 \pi \rho A = 3.41 \ ly$

That sounds right. I'm not sure if there are any binary stars inside the area considered, but if there are then it might make r a bit smaller than we might expect otherwise.

~modest

##### Share on other sites

since what we really want is the average distance to the nearest star system, and atlasoftheuniverse.com reports 23 star systems within 12.5 ly (35 stars but 3 trinaries, 6 binaries, and 14 singles), we have:

rho = 23/([4/3]pi 12.5^3)

rho = 0.0028113 star systems/cubic light-year

rho is only an estimate since some of the star systems near the outer edge of the volume (of 12.5 ly radius) might have nearest neighbors outside the volume and some star systems just outside the volume might have nearest neighbors inside.

since the integral of x^3 exp(-a x^3)dx doesn't seem to be integrable, I used

people.hofstra.edu/stefan_waner/RealWorld/integral/integral.html

to numerically integrate:

the integral from 0 to infinity of 0.035328(x^3)(e^(-0.011776(x^3)))dx = 3.93 light years

as the average distance from an arbitrary star system in the solar neighborhood to its nearest nighbor :)

##### Share on other sites

aswoods at

S.O.S. Mathematics CyberBoard :: View topic - mean nearest neighbor in 3d

helpfully pointed out that Gradshteyn and Ryzhik 3.381.10, and Wolfram Alpha agree that

the integral from 0 to infinity of x^3 e^(-ax^3)dx = 1/3 gamma(4/3) a^(-4/3)

so the mean nearest neighbor distance in 3d is:

<r> = [4 pi rho] integral from 0 to infinity r^3 e^(-[4/3] pi rho r^3) dr

<r> = 1/3 gamma(1/3) ([4/3] pi)^(-1/3) rho^(-1/3)

<r> = 0.55396 rho^(-1/3)

<r> = 3.93 light-years for the 23 star systems within 12.5 ly :)

##### Share on other sites
Hi. In 3 dimensional Euclidean space with the usual metric, d=[(delta x)^2+(delta y)^2+(delta z)^2]^1/2, I'm trying to figure out the average distance between nearest neighbors in a randomly distributed sample of particles.

A very neat problem.

In the spirit of simple modeling over higher math, I tried randomly placing bodies in a fixed volume (area, volume, hypervolume) of space of 2 to 4 dimensions, finding each ones closest neighbors. and the collection’s average and variance:

so the mean nearest neighbor distance in 3d is:

<r> = [4 pi rho] integral from 0 to infinity r^3 e^(-[4/3] pi rho r^3) dr

<r> = 1/3 gamma(1/3) ([4/3] pi)^(-1/3) rho^(-1/3)

<r> = 0.55396 rho^(-1/3)

This agrees roughly with several runs of a simply randomly placing between 100 and 1000 bodies in a cubic volume of space, finding the distance to the closest neighbor of each, and averaging it. I tried this 5 times for a space with coordinates from 0 to 1e6-1 in 1 to 5 dimensions, getting the following:

[font="Fixedsys"][noparse]                    Avg Least  Avg Least distance
Dimensions  Bodies  distance   /Uniform distance   Variance^.5
1           100       4892.70  0.4892702            5173.99887
2           100      53228.70  0.53228708199187    28376.91464
3           125     117107.53  0.58553768698591    48354.27492
4           256     164700.92  0.65880368536226    49878.42215
5           243     242188.68  0.72656605601714    67920.46266[/noparse][/font]

The measured r (“Avg.Least distance/Uniform distance”) appear a bit high, as per trekkiee’s and Modest’s research, it should be 0.5 and about 0.55396 for 2 and 3 dimensions respectively. Increasing the number of bodies appears to lower the measured r, so I pretty sure this is a small sample artifact. My quick program is inefficient, however, so I can’t quickly test this.

Having a variance is nice, as it allows calculation of the likely average distance between stars. The distribution’s not uniform, however, closer I think to a gamma, so it’s easier just used the observed distribution than the variance for this.

I don’t immediately have any real astronomy data to which to apply the 3d findings, however, as I don’t have a good value for the volume and star count of nearby space. The galaxy has a lot of structure, a star-dense core, voids between spiral arms, etc, so just taking the galaxy’s overall dimensions.

What values for volume and star count did you use, trekkiee?

## Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account. ×   Pasted as rich text.   Paste as plain text instead

Only 75 emoji are allowed.

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.