Optimality of the square lattice among Steiner networks

Let the cities be the points {(i,j):i,jZ}\{(i,j): i,j\in\mathbb{Z}\} in the plane, and consider a Steiner network on this square-grid configuration. Its normalized length is its total network length per unit area, and its stretch is the maximum ratio between network distance and Euclidean distance for pairs of cities. Square-grid Steiner-network optimality conjecture. If a Steiner network on the square-grid configuration has stretch at most 2\sqrt{2}, then its normalized length is at least 22. The usual square-lattice network has normalized length 22 and stretch 2\sqrt{2}, so the conjecture asserts its optimality among Steiner networks with stretch at most 2\sqrt{2}.

Sources & referencesView supporting material

Primary source

David Aldous and Tamar Lando, “The Stretch - Length Tradeoff in Geometric Networks: Average Case and Worst Case Study”, arXiv:1404.2653 (2014).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.