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 "nearestneighbor graph" of these point sets? The length of a "nearestneighbor 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_{i1} \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.
1 Answer
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})$.

$\begingroup$ Thanks! Is there a lower bound of the same order using similar techniques? $\endgroup$ Commented Aug 21, 2013 at 6:06