5
$\begingroup$

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?

Improve this question
$\endgroup$
4
  • $\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, 2015 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, 2015 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, 2015 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, 2015 at 22:41

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.