Expected length of a certain kind of nearest-neighbor graph

Question

Suppose I have sets of points $Z_1,\dots,Z_N$, such that $|Z_i|=m$ for all $i$, and where all $m\times N$ points are independently distributed uniformly at random in the unit square. Can someone give me a lower bound within the right order of magnitude of the expected length of a "nearest-neighbor graph" of these point sets? The length of a "nearest-neighbor graph" is defined as $$ \sum_{i=1}^N \min_{z\in Z_i} \min_{\bar{z} \in \bar{Z}_i} \|z-\bar{z}\| $$ where $\bar{Z}_i$ denotes the union of all point sets $Z_j$ other than $Z_i$, i.e. $$\bar{Z}_i:=Z_1\cup \cdots \cup Z_{i-1} \cup Z_{i+1} \cup \cdots Z_N $$ It seems that the answer OUGHT to be $\mathcal{O}(\sqrt{N/m})$, but the tightest lower bound I can come up with has $\mathcal{O}(\sqrt{N}/m)$, which seems much too loose. When I talk about "order of magnitude", I am happy to consider either the case where $m$ is fixed and $N$ becomes large, or the other way around.

Answer 1

Consider $N$ fixed and $m \to \infty$. Partition the unit square into $k^2$ squares of side $1/k$, where $k \approx \sqrt{m}$. Then the probability that no square contains both a member of $Z_i$ and a member of $\overline{Z_i}$ should, I think, be on the order of $e^{-cm}$ for some positive constant $c$ (and I suspect that the theory of Large Deviations can be used to prove this).
So the probability that $\min_{z \in Z_i} \min_{\overline{z} \in \overline{Z_i}} \|z - \overline{z}\| < \sqrt{2/m}$ is at least $1 - e^{-cm}$. The conclusion is that your expected value is $O(1/\sqrt{m})$.