0

I've been looking into RSMT trees recently. For those unfamiliar with them, it's the smallest possible tree that connects a set of points using only vertical and horizontal edges.

One of the features of this tree is what I will call inner vertices. These are points where 3 or 4 edges come together in the RMST tree. Finding these points is the real problem of the RSMT tree, as you could easily construct one if you knew where the inner vertices were.

Thus, after a long introduction, my question is this:

For a given set of points, is there only a single possible set of inner vertices, or are there other possible RSMT trees that have different inner vertices?

Nathan Merrill
  • 506

1 Answers1

1

Let your points-to-be-connected be $A=(0,0)$, $B=(4,3)$, $C=(-3,4)$, and $D=(1,7)$, the vertices of a square. I think you get your tree by letting $E=(0,4)$, $F=(1,3)$, drawing $AE$, $CE$, $DF$, and $BF$, and then drawing a horizontal line to join $AE$ and $DF$. But the vertical location of that horizontal segment, and of the inner points it creates, are not unique.

Gerry Myerson
  • 179,216