Skip to main content
3 of 3
Image links broken; now fixed.
Joseph O'Rourke
  • 150.8k
  • 36
  • 358
  • 958

Shortest grid-graph paths with random diagonal shortcuts

Suppose you have a network of edges connecting each integer lattice point in the 2D square grid $[0,n]^2$ to each of its (at most) four neighbors, {N,S,E,W}. Within each of the $n^2$ unit cells of this grid, select one of the two diagonals at random to add to the network. These diagonals serve as local "short cuts." One could ask many questions about this model, but let me start with this one:

What is the expected length of the shortest path in such a network from $(0,0)$ to $(n,n)$?

Here is an example for $n=25$:
      Shortest path between corners
Here a shortest path has length $10+20 \sqrt{2} \approx 38.3$ in comparison to the shortest possible length, $25 \sqrt{2} \approx 35.4$. For small $n$, the growth rate of the length of the shortest path appears to be linear in $n$, with a slope of about 1.52315.
      Length vs. n
I would appreciate learning if anyone recognizes this model and/or knows the true growth rate. Thanks!

Edit. One more figure to address a question raised by jc. This shows 10 shortest paths for $n=50$, for different random diagonal choices (not shown). But be aware that usually several shortest paths are tied as equally long, and my code selects one with a systematic bias toward the lower right corner. But the figure provides a sense of the variation.
      Short Paths n=50

Joseph O'Rourke
  • 150.8k
  • 36
  • 358
  • 958