# Minimizing maximum distance by adding shortcuts in grid graph

My problem is to find places to put k number of shortcut edges with weight 0 to minimize maximum distance in grid graph where all edges are weighted 1! I found a related topic to my question Minimizing distance on a graph by adding shortcuts but similar to Christopher I don't understand many mathematical concepts.

I've tried to analyze Paper that Christopher found but still don't know how could I implement this to my problem! Trying to be more specified let's look at grid graph:

I want to add k shortcut edges to minimize maximum distance. Example:

So the question in what is the which nodes to connect, and how to prove that this is the best solution!

It's not hard to bound the new distance to within a constant factor, as a function of $k$. If you add $k$ shortcut edges to an $n\times n$ grid, the number of points within distance $d$ of an endpoint of a shortcut will be $O(kd^2)$, so unless $d$ is big enough to make this $n^2$ there will be some points farther from any shortcut endpoint than this. Therefore, the distance will remain at least proportional to $n/\sqrt k$, no matter where you put the shortcuts.
On the other hand, by spacing the shortcuts evenly throughout the grid, you can ensure that every point can reach at least one shortcut within distance proportional to $n/\sqrt k$. And by connecting the shortcuts themselves into a star topology (a tree with one interior node and $k$ leaves) you can make the distances between any two shortcuts negligible. So the best distance you can achieve is both upper-bounded and lower-bounded proportional to $n/\sqrt k$.
• I simplified that part to $O(kd^2)$. It's just counting how many points are within that distance on a grid. $d$ can be any number you want it to be, and the $O(kd^2)$ bound on how many points are within that distance of shortcut endpoints will remain valid. – David Eppstein Dec 30 '17 at 4:45