Given an $n \times n$ grid with unit grid cells, and one point from the interior of each cell, what is are best possible lower and upper bounds for lengths of minimum spanning trees? The lower bound version of problem seems generate trees that are related to the Euclidean Steiner Tree Problem.

If $n < 4$ the problem is easy; but for the $4 \times 4$ grid, we seem to get the familiar tree from the Steiner problem.

Note that each of the end vertices represents several vertices at some small distance from each other. For a $5 \times 5$ grid the problem begins to become interesting. Here is one candidate for a minimum.

My question is, has this problem been studied before?

or boundaryof each cell, i.e., the tree must touch each cell. $\endgroup$ – Joseph O'Rourke May 23 '15 at 13:55