most recent 30 from http://mathoverflow.net 2013-05-23T22:52:09Z http://mathoverflow.net/feeds/question/22592 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/22592/mean-minimum-distance-for-k-random-points-on-a-n-dimensional-hyper-cube Ingdas 2010-04-26T12:20:01Z 2010-07-02T06:37:03Z

<p>Given K points in a N-dimensional (hyper-)cube with all edges length 1. What is the expected minimal distance between 2 points. I found the 1-dimensional case in this topic: <a href="http://mathoverflow.net/questions/1294/mean-minimum-distance-for-n-random-points-on-a-one-dimensional-line" rel="nofollow">http://mathoverflow.net/questions/1294/mean-minimum-distance-for-n-random-points-on-a-one-dimensional-line</a> and I wonder if this can be generalized into multiple dimensions in general. I don't seem to succeed in extending the card analogy in the other topic. Does anyone have any hints as to proceed with this?</p>

http://mathoverflow.net/questions/22592/mean-minimum-distance-for-k-random-points-on-a-n-dimensional-hyper-cube/22599#22599 Suresh Venkat 2010-04-26T14:31:18Z 2010-04-26T14:31:18Z

<p>It depends on what kind of accuracy you are looking for, but you can get a crude bound of the order of $1/K^{1-1/N}$ by breaking the space into K regions and applying a balls and bins argument. </p>

http://mathoverflow.net/questions/22592/mean-minimum-distance-for-k-random-points-on-a-n-dimensional-hyper-cube/30266#30266 Rob Grey 2010-07-02T04:20:56Z 2010-07-02T06:37:03Z

<p>The following paper:</p> <p><em>Bhattacharyya, P., and B. K. Chakrabarti. The mean distance to the nth neighbour in a uniform distribution of random points: an application of probability theory. Eur J. Phys. 29, pp. 639-645.</em></p> <p>Claims to provide exact, approximate, and handwaving estimates for the mean 'k'th nearest neighbor distance in a uniform distribution of points over a D-dimensional Euclidean space (or a D-dimensional hypersphere of unit volume) when one ignores certain boundary conditions.</p> <p>However, Wadim's response is making me feel some concern that the exact problem is much more complex. Please see the paper for the full derivation (and approximate methods), but I'll write the exact expression they converge on using two different method of absolute probability and conditional probability.</p> <hr> <p>Let $D$ be the dimension of the Euclidean space, let $N$ be the number of points randomly and uniformly distributed over the space, and let $MeanDist(D, N, k)$ be the mean distance to a given points $kth$ nearest-neighbor. This yields:</p> <p>$MeanDist(D, N, k) = \frac{(\Gamma(\frac{D}{2}+1))^{\frac{1}{D}}}{\pi^{\frac{1}{2}}} \frac{(\Gamma(k + \frac{1}{D}))}{\Gamma(k)} \frac{\Gamma(N)}{\Gamma(N + \frac{1}{D})}$</p> <p>Where $\Gamma(...)$ is the complete Gamma function.</p> <hr> <p>Wadim - might it be possible for you to provide some feedback about the derivations here vs. the method of box integrals you described in your comment? </p>