Diagonal shortcuts to minimize all-pairs shortest-paths in grid graph

Question

Augment the grid graph $G$ on lattice points $[1,n]^2$, which connects each point to its four distance-$1$ vertical and horizontal neighbors. Augment $G$ to $G'$ by adding in one of the two $\sqrt{2}$ diagonals to each $1 \times 1$ lattice square. I am seeking to understand which selection of diagonal shortcuts will minimize the total length of all shortest paths: all shortest paths between the $\binom{n}{2}$ pairs of lattice points in the augmented graph $G'$. An example $G'$ is shown below.

---

         
          ^$n=7$.

---

Above the shortest path from $(1,1)$ to $(7,7)$ is $4+4\sqrt{2} \approx 9.7$, while the shortest path from $(7,1)$ to $(1,7)$ is $6\sqrt{2} \approx 8.5$.

Q. What is the optimal choice of diagonals to minimize the sum of the lengths of the shortest paths in $G'$ between all pairs of lattice points, for arbitrary $n$?

Perhaps this has been studied before? It seems related to shortest-path trees, but I am not seeing how that concept yields the optimal network in the described situation.

---

Related: Shortest grid-graph paths with random diagonal shortcuts.

Answer 1

Checkerboard pattern is optimal, as long as the top left corner (or, indeed, at least one corner) has an adjacent diagonal.

Observe that the smallest possible distance between opposite corners of an $h \times w$ rectangle in any diagonal orientation is $h + w - (\sqrt{2} - 1)\cdot \min(h, w)$. One can see further that the checkerboard pattern achieves this bound for all rectangles with $h \neq w$, and is short $\sqrt{2} - 1$ to achieve it for about half of square corner pairs. Let us show that no orientation can do better than that.

A corner pair of a square is at optimum distance iff it is connected by an unbroken chain of diagonals. Consider any square with odd side length $k$; clearly, at most one of its diagonals can be unbroken. Hence, there can be at most $(n - k)^2$ optimum corner pairs, a bound that checkerboard readily achieves.

Squares with even side length $k$ require a bit more thought. Let's choose one of two diagonals in each $k \times k$ so that adjacent (= different by a shift of distance 1) squares have different orientations. There are two ways to do that, take any one of them.

Observe that in any pair of adjacent squares, at most one can have an unbroken diagonal of the chosen type. It follows that among the chosen diagonals at most $\lceil (n - k)^2 / 2 \rceil$ can be unbroken (since this is the maximum size of an independent set in an $(n - k) \times (n - k)$ grid). Accounting for two ways to choose orientation, there can be at most $2 \lceil (n - k)^2 / 2 \rceil$ optimal corner pairs in $k \times k$ squares. With a little case work, one can see that this is exactly how many optimal pairs of this kind a checkerboard pattern has.

The same argument seems to apply for $n \times m$ rectangular grids as well as square ones.