For two points $x$, $y \in [0,1]^2$, let their distance be $d(x,y) := \|x-y\|_2^2$ (i.e. the usual distance, squared). Technically, this is a semimetric, as it does not satisfy the triangle inequality.

Given finite $P \subset [0,1]^2$, let $f(P)$ be the length (measured by $d$) of the minimal spanning tree of $P$. What is $\sup_{P \subset [0,1]^2} f(P)$?

A few words about my work so far: I am convinced that $\sup$ should be replaced by $\max$ and that it is 3. I am also convinced that $f$ is maximized by $S := \{(0,0),(0,1),(1,0), (1,1)\}$, uniquely. Given a point set $P$ and a minimal spanning tree, note that any two points $x,y \in P$ define a circle, with $\|x-y\|$ its diameter. If the edge $(x,y)$ is in the spanning tree, then adding a new point to $P$ within this circle creates a shortcut, reducing the size of the spanning tree. Adding a point $z$ on the circle changes nothing locally, as $d(x,y) = d(x,z) + d(z,y)$. Since the points in $S$ can never create a shortcut, $f(S \cup P) \geq f(P)$ for all $P$. Therefore, $$\sup_{P \subset [0,1]^2} f(P) \leq \sup_{P \subset [0,1]^2} f(P \cup S).$$

Unfortunately, the size of a minimal spanning tree is not monotonic. $f(S) = 3$, while $f(S \cup (0.5,0.5)) = 2$, but it is possible to add more points and again increase $f$.

This problem seems Putnam-esque, but I don't recall its origins. For all I know, it is open, but I would appreciate any thoughts on it.

  • $\begingroup$ Can you show (or refute) that if P is a point set with a minimal spanning tree with a point p of degree 3, that P takeaway p gives a pointset with longer minimal spanning tree? Gerhard "Ask Me About System Design" Paseman, 2013.04.22 $\endgroup$ – Gerhard Paseman Apr 22 '13 at 19:31
  • $\begingroup$ @Gerhard: not off the top of my head, but the situation I envision has this $p$ in the middle of 3 other points, and thus inside of some of the circles I was speaking about. That would imply that $p$ is a shortcut and removing it would increase $f(P)$. Basically, I don't know, but I will think about it. $\endgroup$ – Eric Tressler Apr 22 '13 at 19:37

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.