# What is the distribution of the maximum nearest-neighbor distance of a point cloud sampled from a solid body like?

Let $\mathcal{B} \subseteq \mathbb{R}^n$ be an $n$-dimensional solid body. Assume that we sample $N$ points, say $S = \{ x_1, ..., x_N \}$, from $\mathcal{B}$ uniformly at random. Consider the following random variable:

$$D \equiv \sup_{x \; \in \; S} \; \inf_{y \; \in \; S} \; d(x, y) \; .$$

Intuitively, this variable measures the distance of the "worst" outlier to the rest of the sample set. The distribution of $D$, say $p(D)$, obviously depends on $N$ and $\mathcal{B}$. I am curious about the following:

(1) Are there any closed form expressions known for certain special cases like $\mathcal{B} = [0, 1]^n$ or $\mathcal{B}$ being the unit $n$-ball?

(2) Can we say anything about the dependence of $p(D)$ on $N$ without fixing $\mathcal{B}$? Obviously, $D \to 0$ as $N \to \infty$, but can we say more?

• In other terms, you seek the maximum nearest-neighbor distance. It may be already somewhat interesting to restrict to points selected from an interval of $\mathbb{R}^1$. (And note that the "worst" outlier could be in the center of the set.) May 11, 2015 at 22:55
• @JosephO'Rourke Agreed. A succinct result for an interval of the form $[0, U]$ could be illuminating for the purposes of estimating the dependence of $p(D)$ on $\mathcal{B}$'s size (represented by $U$ in this case) and sample count $N$. May 11, 2015 at 23:08
• @JosephO'Rourke I changed the title of the question to use the wording you mentioned. It definitely sounds more natural than what I had in the first place. May 12, 2015 at 1:37
• In the case of the interval, the maximum is $2/N,$ roughly. What this tells you about the general case is anyone's guess :) May 12, 2015 at 1:38
• Call the $i$th gap $X_i$. Set $Y_i=\min(X_i,X_{i+1})$. Then $Y_i$ is independent of $Y_j$ whenever $|i-j|>1$. Given $N/2$ independent $\text{Exp}(2N)$ random variables, the maximum is approximately $\log N/(2N)$. May 12, 2015 at 5:33

You can make the calculations for a cube with the $L_\infty$ distance and the uniform distribution and you simplify the problem a little bit by letting $X_i$ be independent of $Y_i$ you can say the following: let $X = (x_1, \ldots, x_n)$ then

$$d(X,Y) = \max_i |y_i - x_i|.$$

By letting $a_i = \min(x_i, 1 - x_i)$ and $b_i = \max(x_i, 1-x_i)$, we see the distribution of $d(X, Y)$ is given by

$$F_X(z) := P(d(X,Y) \leq z) = \prod_{i=1}^n 2 z 1_{z \leq a_i} + (z + a_i) 1_{z \in [a_i, b_i]} \geq 2^n \prod a_i 1_{z \in [a_i, b_i]}$$

This implies that $P(\max_{i \in 1, \ldots, N} \min_{j \in 1, \ldots, N} d(X_i, Y_j) \leq z) = \prod_{i=1}^N 1 - \int_{[0,1]^n} (1 - F_{X_i}(z))^N dX_i$, which we can lower bound by $\prod_{i=1}^N 1 - \int_{[0,1]^n} ( 1 - 2^n \prod_{j=1}^n a_j 1_{z \in [a_j,b_j]})^N dx_1, \ldots dx_n$. We can now upper bound the integral by $$\int_{[0,1]^n} \exp \Big(-N 2^n \prod a_j 1_{z \in [a_j, b_j]}\Big)$$

Now, using the fact that the product is smaller than $z^n$ when $z <1/2$ and the convexity of the exponential function it is easy to see that the above integral is bounded by $$1 - \frac{\int \prod a_j 1_{z \in [a_j, b_j]}}{z^n} + \frac{e^{-N (2z)^n} \int \prod a_j 1_{z \in [a_j, b_j]}}{z^n}$$. A straightforward calculation shows that the integral above is equal to $z^n$ therefore the previous expression is equal to $e^{-N (2 z)^n}$

We therefore have $$P(\max_{i \in 1, \ldots, N} \min_{j \in 1, \ldots, N} d(X_i, Y_j) \leq z) \geq (1 - e^{-N (2 z)^n})^N \approx e^{-N \exp(-N (2z)^n)}$$

This tells you that roughly the distance of the maximum outlier to the rest of the points is $\frac{\log N}{N^{1/n}}$ this will be true for any norm because they are all equivalent up to a n^{1/2} factor. It seems the dependency on $n$ is terrible by the way which makes you wonder why people use nearest neighbor algorithms. I am not sure how much more you can improve the bound. Then only place where I was extra generous with my bound was in (1), so maybe there you can tighten it a little more but honestly I do not see how you can get rid of the $z^n$ factor in the bound.

• Actually I just realized that F_x(z) \leq z^n all the time so I think you can in fact not get rid of the z^n factor. May 13, 2015 at 20:26