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.


1 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})$.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.