My question is the following: Given $N$ uniform IID points $X=(X_1,...,X_N)$ on the unit cube of $\mathbb{R}^d$, take $X_1$ and another point, say $X_{(1)}$, "close" to $X_1$ (i.e. connected to $X_1$ through the Delaunay graph on $X$). How can I get a bound on the distance between $X_1$ and $X_{(1)}$ within the MST (minimum spanning tree) on $X$. (more precisely, a bound on supremum over all possible neighbours $X_{(1)}$). I am also interested in the case where $X$ is a homogeneous Poisson process with intensity $N$.

My original concern is simply a bound on the length (in terms of number of vertices) for a connected path between $X_1$ and $X_{(1)}$ with edges of euclidean length $<\|X_1-X_{(1)}\|$ and vertices in $X$. But the MST-related path described above fulfills this condition.

By imagining a fixed homogenous Poisson process within a growing window $W_N=[-N^{1/d},N^{1/d}]$, one can simply track the MST-distance $d_N$ between a point arbitrarily labelled $X_1$ within the Poisson process and one of his Delaunay-neighbours $X_{(1)}$ as $N\to \infty$. At least in dimension $2$, $d_N$ might converge to a fixed number $\delta$, which is actually the one I would like to bound. Ideally I would like to prove that $\mathbb{E} (\delta^{2+\epsilon})<\infty$ for some $\epsilon>0$.

In the topic What upper bounds are known for the diameter of the minimum spanning tree of $n$ uniformly random points in $[0,1]^2$?, the author asks about the diameter of the MST on $X$ for the graph distance, but this diameter is much larger than the bound I am looking for because $X_1$ is taken at random and also the second point is "euclidean-close" to $X_1$, probably implying that it is also "MST-close" with high probability.

  • $\begingroup$ The question on the MST (first paragraph), although it interests me, is probably more difficult than my original concern (second paragraph). For this question I also created the following post mathoverflow.net/questions/128912/… $\endgroup$ – kaleidoscop Apr 27 '13 at 10:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.