# Reversing shortest paths among unit disks

Twas the night before Christmas, and throughout M.O.
Not a question was posted, not even by Joe.


Well, let me remedy that. :-)

Let the plane contain a number of pairwise disjoint open unit-radius disk obstacles. Because they are open, their bounding circles can touch tangentially. Shortest paths between two points $a$ and $b$ in the complement of the disks generally look like this:

Notice that the (red) path from $a$ to $b$ is monotonic with respect to the line containing $a$ and $b$—it meets every line orthogonal to $ab$ in a single point—and in that sense never "reverses direction." However, it is possible for a shortest path to reverse direction, e.g.:

Here the red path, which reverses direction slightly near $b$, is a bit shorter than the blue path: $$\pi + 2 + \epsilon < \frac{5}{3}\pi - \epsilon$$ $$5.14 + \epsilon < 5.24 - \epsilon$$ for sufficiently small $\epsilon$, e.g., $\epsilon = 5^\circ$.

However, I am hoping this has a positive answer:

Q1. If the disks form an infinite hexagonal penny packing, are all shortest paths (between pairs of points in the complement of the packing) monotonic with respect the line through the endpoints?

More generally:

Q2. If the disk centers form a regular lattice of $\mathbb{R}^2$, are all shortest paths monotonic?

Here I am not requiring that the disk boundaries be tangent, but rather just that the disks form a regular array. I am wondering if it is irregularity that allows nonmontonic geodesics.

The context is that, perhaps, in disk arrangments where the shortest paths are monotonic, the $O(n^2)$ algorithms for finding a shortest path amidst $n$ disks can be improved to subquadratic.

• Maybe I'm missing something, but isn't your second example already a counterexample to Q1? – Rodrigo A. Pérez Dec 24 '13 at 15:37
• @RodrigoA.Pérez, I think that Q1 refers to the packing of the entire plane, not just a little piece of it. – Gerry Myerson Dec 24 '13 at 16:34
• @RodrigoA.Pérez: Gerry is correct. Apologies for the lack of clarity. Repaired now. – Joseph O'Rourke Dec 24 '13 at 17:56
• Consider a proof by induction. Given a point a, show that all points in a ball centered at a with a radius of r+epsilon have such a monotonic path given all point in an r-ball have such paths. – The Masked Avenger Dec 24 '13 at 19:43
• Yes, and that field of disks lacks sufficient symmetry (and also has a counterexample) for an induction proof to work. I suggest a proof by induction as one way to capitalize on the regularity of the space. To make it more real, here is a suggestion: Look at the circles intersecting the line between a and b; there is a shortest path involving only those circles and some of their neighbors. – The Masked Avenger Dec 25 '13 at 16:54