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.

4more comments