Minimum weight spanning trees of point-sets in the unit square (YEAR)

Originators: [ABDKR]    (presented by Andrew King - REGS 2011)

Definitions: Let $S$ be a set of points in the unit square $[0,1]^2$; the distance between points $p_1$ and $p_2$ is denoted $||p_1-p_2||$. Weight each edge $p_1p_2$ by $w(p_1p_2) = ||p_1-p_2||^{c}$, where $c \geq -2$, and let $M_c([0,1]^2)$ be the supremum over all $S$ of the minimum weight of a spanning tree for $S$.

Background: When $c\gt -2$, there are examples illustrating that $M_c([0,1]^2) = \infty$. Finding such an example is a straightforward exercise. What about for $c=2$? Clearly $M_2([0,1]^2) \geq 3$, as we can see by letting $S$ be the four corners of the unit square. This lower bound is fairly close to the best known upper bound; [ABDKR] proved $M_2([0,1]^2) \lt 4.$ We seek better bounds.

Conjecture: $M_2([0,1]^2)=3$.

Comments: To prove the upper bound of 4, one first proves the optimal result for certain triangles: If $T$ is the set of corners of a right-angled triangle with hypotenuse length $h$, then $M_2(T)=h^2$. After proving this, bounding $M_2$ for the unit square is fairly straightforward. First, prove that $M_2([0,1]^2)$ is achieved by some pointset that includes the four corners. Then split the unit square into two congruent triangles with hypotenuse length $\sqrt 2$, find a minimum weight spanning tree of each, and take the union of these two trees. Since the intersection of the two subsets contains two corners, what remains is a graph with at least one cycle, so we can remove the largest edge of this cycle and still have a connected spanning subgraph of $S$.

This problem was considered by Gilbert and Pollack [GP] for the unit ball; inscribing the unit ball in a square improves their bound.

Several observations have been made about a minimum weight spanning tree $T$ for a given point set.