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.



Expected length of a certain kind of nearest-neighbor graph
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})$.


