24
$\begingroup$

Let $P$ be a pointset consisting of $n$ uniformly random elements of $[0,1]^2$. It is known that the diameter (greatest number of edges in any shortest path between two points) of the Delaunay triangulation of $P$ has expected order $\Theta(\sqrt{n})$; the upper bound follows from work by Bose and Devroye, and the lower bound follows from a more general result on weighted Delaunay triangulations by Pimentel.

Since the Euclidean MST $T=T(P)$ is a subgraph of the Delaunay triangulation, it follows that $T$ has expected diameter of order at least $\sqrt{n}$. It seems a plausible guess that the expected order is in fact $\Theta(\sqrt{n})$. However, I know of no non-trivial upper bound on the expected diameter of $T$. (In particular, I don't even know if it is $o(n)$ -- or even if it is less than, say, $n/10$.) Do you?

What upper bounds are known for the expected diameter of $T$, the minimum spanning tree of $n$ uniformly random points in $[0,1]^2$?

$\endgroup$
6
  • $\begingroup$ Excuse me: for clarity: you mean: an upper bound for the expected value of the diameter of the MST, don't you? (Thus not an upper bound for the MST of all n−ples of points, that's independent from the distribution). $\endgroup$ Sep 15, 2010 at 16:28
  • $\begingroup$ Yes, thanks for the clarification. I'll make this more precise in the question. $\endgroup$ Sep 15, 2010 at 17:34
  • 1
    $\begingroup$ The diameter of a random spanning tree of $K_n$ is also $\sqrt{n}$, a result of Renyi and Szekeres from the 1960s. More support for your conjecture. $\endgroup$ Sep 15, 2010 at 18:08
  • 4
    $\begingroup$ Joseph, that's true if you take a uniform spanning tree but if you put IID weights on the edges (say Uniform[0,1] weights) then the expected diameter of the MST drops to $n^{1/3}$. Heuristics from statistical physics suggest that this should mean that in high dimensions, i.e., in $[0,1]^d$ for, say, $d \geq 6$, the diameter of the MST of a random pointset would in fact be $n^{1/3}$. $\endgroup$ Sep 15, 2010 at 18:17
  • $\begingroup$ Which is to say: I'm not sure whether or not it's coincidence that the answer for a uniform spanning tree of $K_n$ is $\sqrt{n}$. $\endgroup$ Sep 15, 2010 at 18:18

3 Answers 3

33
$\begingroup$

Added: What can we expect from the Euclidean MST

After mulling over this question for a few days, I think it's inconsistent with the stated facts that the diameter of the Euclidean MST is $\Theta(\sqrt n)$. Here's why.

Let's first interpret the theorem mentioned in the question: that the diameter of the Delaunay triangulation for $P$ has expected diameter $\Theta(\sqrt n)$. For each $n$, the Delaunay triangulations for $P$ define a probability measure on the space of metrics on $n$-element subsets of the unit square. We can interpolate this metric to a metric on the unit square by making each triangle of the Delaunay triangulation an equilateral triangle, and rescale it by $1/\sqrt n$ to get a measure on the space of metrics on the square. As $n$ goes to infinity, these metrics have uniformly bounded $\epsilon$ complexity (=minimum number of balls of size $\epsilon$ needed to cover). The set of metrics of $\epsilon$-complexity bounded by some fixed function of $\epsilon$ is compact in the Gromov-Hausdorff topology, so the space of probability measures on these metric spaces is compact in the weak topology, so there exists at least a subsequence of $n$ such that the scaled Delaunay metrics converge to a measure on metric spaces.

The metric spaces are a.s. Lipschitz equivalent to the standard metric on the unit square, using the theorem about diameter (which can be used to deduce that the Delaunay distance between two random elements $p, q \in P$ is $O(\sqrt n)$). These metrics are path-metric spaces. The shortest paths are rectifiable arcs in the Euclidean sense as well as in the particular metric, since the two metrics are Lipschitz equivalent. A rectifiable arc in the plane has a tangent line almost everywhere, so there are rescaled limits where almost all limiting Delaunay geodesics are straight lines.

Proposition: The rescaled Delaunay metrics converge a.s. to a constant multiple of the Euclidean metric in the plane.

That the metric of the plane is the actual limit, not just a limit point, follows from considerations parallel to the fact that a rescaled limit of a Lipschitz function is a.s. linear. If there were any significant probability of significant deviation at any stage, these would accumulate and prevent the large-scale map from being Lipschitz.

Now consider the Euclidean MST for a Delaunay triangulation as a metric tree. Suppose the trees have probable diameter is $\Theta(\sqrt n)$. For each pair of points $x$ and $y$ in the unit square and for each $P$, let $x_P$ be the point of $P$ closest to the $x$, let $y_P$ be closest to $y$, and let $\gamma_P$ be the path in the MST connecting $x_P$ to $y_P$, parametrized by $1/\sqrt(n)$ times the combinatorial Delaunay distance. In the limit, the measure on $P$'s would converge to a probaility measure on rectifiable paths from $x$ to $y$. But more than that, we would get a measurable map from the square cross the square that takes each pair of points to a rectifiable path between them, with arclength less than some constant times their distance.

This is not topologically compatible with the tree-like condition: near the boundary between two large branches of a tree, the tree distance between points on one branch to points on the other branch is a large multiple of the distance in the plane.

To test my understanding, I ran simulations (using Mathematica's Computational Geometry package and Combinatorica package). Here are two Euclidean MST's, the first with 1500 random points in the unit square, the second with 10,000. You can plainly see that paths connecting pairs of vertices are not converging to rectifiable, Lipschitz paths.

alt text

alt text

As a further test, I calculated the diameter of the Euclidean MST's for 25 uniform pseudo-random distributions of $2^k$ points, for each $k$ ranging from 2 through 8. The sample mean diameters are {2.64, 5.8, 10.32, 18.32, 29.88, 49.12, 78.88}. The best linear fit to to the log of the diameter as a function of $k$ is $.03 + .55 k$. The sample standard deviations for the log of the diameter were nearly constant, all about .15. (that is, the diameters fluctuate on a multiplicative scale, typically about $\pm 16 \%$). It's curious that $Exp[.55] = 1.733$, close to $\sqrt 3 = 1.732$. This suggests a power law that asymptotic diameter $\approx n^{]log(\sqrt 3 / 2)}$, but this could be coincidence, since the numerical experiment was modest in size. Here's the plot of log of mean sample diameter vs. $k$:

alt text

The actual asymptotic behavior of diameter seems intricately tied with percolation, a subject that I do not understand very well. That is: you can think of building up the MST by successively adding edges of length $t$ if they join points on different connected components. This gives an increasing union of equivalence relations on elements of $P$, consisting of clumps that can be connected by steps not greater than $t$. One would expect that for $t$ greater than some critical distance $t(n)$ that is approximately a constant time $1/\sqrt n$, large-scale clusters are likely. Paths between points in the a clusters must stay in the cluster. The geometry of the increasing clusters should enable one to estimate the Hausdorff dimension of tree geodesics, which should in turn give an exponent of growth for the diameter of the Euclidean MST.

The Mathematica notebook containing these computations is here. The code in the notebook itself is brief, since algorithms for Delaunay triangulations and minimum spanning trees and graph diameter are provided in packages in the Mathematica distribution. It took me more effort to make it work than it should have, because functions in these auxiliary packages are poorly documented. Here are some simple ideas for better showing what's happening, and analyzing further:

  1. Draw the Delaunay triangulation in a different color, along with the tree
  2. Indicate the increasing clumps accessible with changing step size by edge thickness and/or color coding edges of the spanning tree. One idea is to use random colors for short edges within clumps, then use a saturated average color (with average weighted by clump size) when new edges make clumps collide and merge. Delaunay triangles could also be color coded to indicate clumping.
  3. Make a 3-dimensional plot of graph distance from a randomly selected member of $P$ to other elements of the tree, using the TriangularSurfacePlot function from the ComputationalGeometry package. Also: try showing distance from basepoint by color coding, perhaps
  4. Do bigger experiments, and make plots showing the actual data: e.g. make a ListPlot[] of the log of the actual diameter for trees of sizes something like Floor[Exp[ Range[2,6,.01]]], but start with a much more modest range and aim for a more ambitious range.
  5. Draw contour plots or 3-D plots of Delaunay graph distance from a randomly selected vertex. How quickly do the contour lines begin to look like circles as the size of $P$ increases?

The following is an earlier answer, which essentially shows that Delaunay "arc length" converges to a multiple of Euclidean arc length. Missing point: how much might larger detours around radars shorten the paths?

Geometry of the Delaunay triangulation.

Let's look at this problem on the surface of a sphere, instead of the unit square. The Delaunay triangulation of a set $P$ on the sphere is invariant under Moebius transformations (easy to verify by the definition in terms of circles), and it is equivalent to the triangulation of the convex hull of $P$. A set in the plane can be transformed to the sphere by stereographic projection. Its Dealaunay triangulation is equivalent to a subset of the polyhedron, namely the part on the far side from the center of projection. The problems, for the uniform distribution on the square and the uniform distribution on $S^2$, are equivalent, but the spherical setting has more symmetry.

In the projective ball model of hyperbolic space, the convex hull inherits a metric as a hyperbolic surface of finite area. I want to describe a related metric. Imagine there is a radar installation at each point of $P$, and that a smuggler wants to fly a small plane below the horizon of any radar. They need to slow down when they're flying lower, at a speed proportional to the distance to $P$, so the metric will be 1/minimum distance to $P$ times spherical arc length. Near an element of $P$, this metric is asymptotically that of a cylinder of circumference $2 \pi$, but slightly smaller near where it is attached because we're rescaling the spherical metric, rather than the Euclidean metric.

Define a "thick" part of $S^2 \setminus P$ to be the set $Q$ obtained by removing a disk around each element of $P$ whose radius is 1/3 the distance to its nearest neighbor.

[Inessential mathematical sidenote: this metric is comparable to the Poincaré metric in Q, except in situations where $P$ is confined to a tiny disk on the sphere. The definition could be modified for that situation, but it's a distraction. The smuggling metric is also comparable to the hyperbolic metric on the image of $Q$ projected to the nearest point in the convex hull of $P$.]

Claim: the smuggling diameter is comparable to the diameter of the Delaunay triangulation.

Proof of Claim: The boundary circles of $Q$ all have comparable circumference in the smuggling metric, slightly less than $2 \pi$. The Delaunay triangles all have diameter bounded above and below in the smuggling metric. This gives an easy way to transform a path in the 1-skeleton of the Delaunay triangulation to a path in $Q$ without increasing length more than a bounded factor. Conversely, for a path in $Q$, the rate of near-encounters with elements of $P$ per smuggling distance is bounded. Therefore, you can do a simplicial approximation, pushing the path to the 1-skeleton with number of edges less than a bounded multiple of its length.

Let's now consider a variation of the problem: A smuggler wants to go between point $X$ on the sphere and point $Y$ on the sphere, in the presence of $N$ uniformly randomly distributed radar installations. The smuggler is conservative, and decides to never exceed spherical speed $N^{-.5}$. This will be less than speed 1 in the smuggling metric except when there is a radar within distance $N^{-.5}$. The density of the set of points is $4 \pi / N$ and the strip has area about $d(X,Y) * 2 N^{-.5}$, so the expected number of radars in the strip is $\Theta(\sqrt N)$. The distribution (Poisson) has standard deviation proportional to square root of expectation, so for moderately large $N$ it is extremely unlikely that there will be more than twice the expected number within the strip: enough that even that the probability that the $\sup$ number over all $X$ and $Y$ tends rapidly to 0 with $N$.

For each radar dish that is within the strip, the smuggler merely takes a detour around the corresponding boundary circle of $Q$, adding only a constant amount of time to the trip. This gives a path in the smuggling metric of $S^2 \setminus P$ with length $\Theta(\sqrt N)$. We want to know the length of a path in $Q$. This is now easy, since there is a distance-decreasing retraction from $S^2 \setminus P \rightarrow Q$: each cylinder can be mapped to its boundary without increasing lengths.

Therefore, the expected maximum diameter of the Delaunay triangulation is $O(\sqrt N)$

This post should really have pictures ... maybe later, or maybe someone else can supply them.

$\endgroup$
25
  • 1
    $\begingroup$ @Bill, yes, I see. It sounds to me like saying $F$ has no local minimum in the complement of $T$ is the right kind of thing but I need to think it over a little. Also, now that I've done some absorbing: unless I'm mistaken the argument in your answer in fact gives an upper but not a lower bound on the diameter of the Delaunay. For the lower bounds you run into the issue of ensuring that there is no clever path the smuggler can take that on the whole stays quite far from radar installations. $\endgroup$ Sep 17, 2010 at 2:42
  • 1
    $\begingroup$ @Louigi: You're right, I didn't give the lower bound. I think it follows from similar considerations, but I should think through how best to organize it. How difficult is Pimentel's proof? My strategy would be: the diameter of the smuggling metric ~ the Delaunay metric, already discussed. But the smuggling metric restricted to Q doesn't fluctuate too badly from the metric of the sphere. One image that would do it: a line of unlicensed peddlars goes across, trying to intercept most of the roads of the Delaunay triangulation while avoiding the towns, with not too many peddlars on any one road. $\endgroup$ Sep 17, 2010 at 5:53
  • 2
    $\begingroup$ I used Mathematica's Combinatorica package and Computational Geometry Package to generate Euclidean MST's for some sets of points. I'm more convinced now. I'll insert figures $\endgroup$ Sep 19, 2010 at 0:47
  • 1
    $\begingroup$ @Bill, OK I'm now convinced the answer is unlikely to be $\Theta(\sqrt{n})$. Thanks very much for giving my question such a good think! Any chance you could post a link to your code? I'd like to fiddle with it, perhaps draw some MST geodesics in red, and also perhaps draw some partial MSTs to explore the connection with percolation a bit more. $\endgroup$ Sep 19, 2010 at 10:18
  • 1
    $\begingroup$ @Peter Shor: Ps: here's data from another version of the experiment, this time it's the mean log diameter, for 2^k, {k,2,8}, again 25 trees for each diameter. {1.03374, 1.71446, 2.30459, 2.91138, 3.41588, 3.92263, 4.37669} Here's what Mma says, when I try to fit: Fit[Log@data1, {1, x + 1, Log[Log[2^(x + 1)] Sqrt[x + 1]]}, x] -0.417826 - 0.0852807 (1 + x) + 0.933709 Log[Sqrt[1 + x] Log[2^(1 + x)]] giving a much bigger coefficient to $\log(n \sqrt n) )$. The data in the answer though has more balanced coefficients. $\endgroup$ Sep 20, 2010 at 4:59
4
$\begingroup$

A colleague, Nicolas Broutin, who is not on MO, pointed me to a recent "preliminary report" of Gábor Pete, about joint work with Christophe Garban and Oded Schramm, on the scaling limit of the MST. In the references of that note I found a paper of Aizenmann et.al. which contains the following information about a suitably defined (subsequential) scaling limit of the MST (I won't get into the precise definition of the scaling limit as it's not particularly important for this answer):

The branches of all trees in $\mathcal{F}(\omega)$ are random curves $\mathcal{C}$ with Hausdorff dimensions bounded above and below: $d_{\mathrm{min}} \leq \mathrm{dim}~\mathcal{C} \leq d_{\mathrm{max}}$, for some non-random $1 < d_{\mathrm{min}} < d_{\mathrm{max}} < 2$.

A couple comments are in order.

First, the paper in fact shows that this result holds for any of three models: uniform spanning tree on the lattice (the limit is as the lattice spacing goes to zero); minimum spanning tree on the lattice with iid uniform bond weights (this is the one most naturally connected with percolation); and third, Euclidean MST on a Poisson point process with intensity $r$ (where the rescaled limit is as $r \to \infty$ appropriately). The last of these is the one most directly connected with my question.

Second, the reason for "all trees" is because the scaling limit is in fact described in terms of a graded collection of finite trees spanning any finite collection of points in one-point compactification of $\mathbb{R}^2$, and satisfying certain consistency conditions. In the paper they show that the collection also turns out to "describe a single spanning tree" in the sense that for sets of points in $\mathbb{R}^2$ (i.e. not including the point at infinity), the tree in $\mathcal{F}(\omega)$ spanning them stays within some finite region in $\mathbb{R}^2$. (Edit: this explanation of "all trees" replaces an earlier false explanation which was based on an overhasty reading of the results.)

Third, given the answer and comments of Bill Thurston, this suggests that the diameter should indeed scale like $n^{\alpha}$ for some $1/2 < \alpha < 1$. (Though, inspired by Peter Shor's comment, I will also mention that it doesn't a priori rule out scaling behaviour of the form $n^{\alpha}\log^{\beta} n$.)

$\endgroup$
1
  • $\begingroup$ You're right ... this indeed shows that the diameter should scale like $n^\alpha$ with $1 > \alpha > 1/2$. It doesn't seem that they have any better bounds on the exponent, though. $\endgroup$
    – Peter Shor
    Sep 20, 2010 at 14:26
1
$\begingroup$

If we consider random pointsets from $[0,1]^d$ (for some large $d$) instead from $[0,1]^2$, then the expected lengths $L_{MST}$ of a minimum spanning tree and $L_{TSP}$ of a travelling salesperson tour are known: $E[L_{MST}] = (1+o(1)) c_{MST} \sqrt{n}$ and $E[L_{TSP}] = (1+o(1)) c_{TSP} \sqrt{n}$, where the constants satisfy, for $d\to\infty$

$c_{TSP} = (1 + o(1)) \sqrt{d/2\pi e} = (1+o(1)) c_{MST}$.

[the precise results are by Bertsimas and Ryzin, OR Letters 9, 1990, and Rhee, RSA 1992]

In particular, the length of the MST and the length of the TSP are very close to each other. This might suggest that the TSP and MST are similar (for large $d$), in the sense that the intersection of the corresponding subgraphs is large. This however, with some additional work, could imply that the diameter of the MST is also quite large.

$\endgroup$
1
  • $\begingroup$ Hi Kostas! As I mentioned in the comments to the original question, the heuristic from percolation is that for $d$ large, the MST should behave like the MST of the complete graph, and hence have diameter of order $n^{1/3}$. So, although the total lengths of the TSP and the MST are asymptotically equivalent, I expect their diameters to be rather different. $\endgroup$ Sep 21, 2010 at 12:22

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.