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.

MST on 4x4 Grid

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. enter image description here

My question is, has this problem been studied before?

  • $\begingroup$ Note that clearly, the optimal solutions are Steiner trees for a collection of certain grid points, with most (possibly not all) of them on the boundary of the inner $(n-2)\times (n-2)$ square. $\endgroup$ – Wolfgang May 18 '15 at 11:45
  • $\begingroup$ The minimum tree length should be something like $c n^2$ I would suppose, since there are $n^2-1$ edges and many of them something like unit length. $\endgroup$ – user48028 May 19 '15 at 3:39
  • $\begingroup$ "from the interior of each cell": Your drawings indicate: from the interior or boundary of each cell, i.e., the tree must touch each cell. $\endgroup$ – Joseph O'Rourke May 23 '15 at 13:55
  • $\begingroup$ Some of those end vertices are supposed to represent several vertices within a very small distance of each other. I'll take it either way, vertices on the boundary or restricted to the interior. $\endgroup$ – user71114 May 23 '15 at 22:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy