Chasing puppies in computational geometry

What do playful puppies and computational geometry have to do with each other? A lot, as it turns out. Today, Tillmann Miltzow and his colleagues are presenting a research paper at the International Symposium on Computational Geometry, the most important conference in computational geometry. In his poetic text below, Miltzow explains the problem they investigated and shares the positive results: in the end, you will always be reunited with your puppy.

The winter was cold, gray and rainy.
Everyone feels soggy and a veil of somber
lies over the eyes of the people.
You walk every morning with your puppy more
out of a sense of duty than enjoyment.
Even the puppy seems to be happy to get back inside.

One day in March, the clouds disappear, sky
and the sun crop out and singing birds come out of hiding.
It seems the perfect day to go for a walk around
one of the lakes in the north of Utrecht.
You let your puppy off the leash and enjoy the blossoms
of the cherry trees.
Your puppy runs around playing with other dogs
too excited to notice anything around herself.

Yet, later that day as all good things also this
outing has to come to an end.
The sun sets slowly and a sudden chill creeps under your skin.
It is time to go back home.
Luckily, you attached a GPS signal to your puppy and
a detailed map helps you to know its precise location.
Your puppy equipped with an instinct that arises from
a mixture of naive loyalty, good will and general friendliness
runs with sheer infinite speed in your direction.
There should be no problem for the two of you to reunite.
There is only one track around the lake and if the puppy just 
runs around the track she would meet you in no time.

If only it would be so easy. 

Too young to understand the topology of a simple circle
she stops in the middle of the track, if going further or backwards
would increase the distance between the two of you.
She only moves after you changed your position again.
Thus, you need to find a way to walk up and down the track
such that the two of you meet each other.

A simple strategy suggests that just walking around the
the track just once should work.
Surprisingly, there is an example, where walking around the track
infinitely often without changing the direction will not
unite you with the puppy.

As researchers we ask ourselves: Is it always possible that the two of you can always reunite, independent of the shape of the track and the starting positions?

Our research established that this is always possible!

In Mathematics, we often encounter statements that are intuitive and appear almost obvious, yet to prove them rigorously occurs to be surprisingly tough. Let us mention here Kepler’s conjecture that states that oranges are most densely packed if you pack them in the obvious way. Despite the fact that there aren’t even much different ways one could pack oranges in the first place, it took almost 400 years to prove Kepler’s conjecture.

The problem we study here is similar. Albeit it appears very simple, finding a mathematical proof turned out to be much more challenging than originally anticipated. Interestingly, our arguments are non-constructive. In other words, we can show that there is always such a possibility, but our proofs give no indication on how such a strategy to reunite with the puppy could look like.

Intriguingly the following strategy could work: walk around the track clockwise once and then counter clockwise.

We neither have a counter-example nor the faintest idea on how to show this.

This research was conducted while Jeff Erickson was visiting Utrecht University in 2019.