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

Question

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?

Answer 1

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.