Pokémon Go Efficiency

To clarify, we know there are $N$ Pokéstops but not how they are arranged. The question asks us to find the smallest and largest possible value for the minimum tour that visits each Pokéstop and returns to the starting point.

Upper bound

The worst-case arrangement of Pokéstops is to have them lie in a line, which leads to a path length of $2(N-1)$. Proving that this is indeed the worst possible arrangements of stops is a bit more involved, so read on if you’re interested.

Let $T$ be a minimum spanning tree for the set of Pokéstops. Any tree with $N$ nodes has $N-1$ edges, so $T$ has $N-1$ edges. It also follows from the adjacency property of Pokéstops that each edge of $T$ must have length $1$. One way to visit all the nodes is by using a depth-first tree traversal:

• Imagine all edges of $T$ are initially colored black.
• Pick a node at random to be the current node.
• Find a black edge emanating from the current node. Paint that edge blue and follow it to the next node, which becomes the new current node. If there are no more black edges, follow a blue edge instead and paint it red.
• Repeat until all edges are painted red.

This process clearly visits all the nodes and visits each edge exactly twice, for a total tour length of $2(N-1)$. This construction works for any arrangement of Pokéstops. Of course this is merely an upper bound; the optimal path may be shorter. By arranging the $N$ stops in a line, we attain our upper bound of $2(N-1)$, so it must be a tight bound.

Lower bound

Since the Pokéstops lie at integer coordinates, the shortest possible distance from one to the next is $1$. So a path visiting $N$ Pokéstops and then returning to the start has length at least $N$. Does there exist an arrangement of Pokéstops that achieves this minimum? If $N$ is even, the answer is yes; arrange the stops in a $2\times N$ grid:
If the number of stops is odd, however, it’s impossible to arrange them in a way that creates a tour of length $N$. To see why, imagine that the stops are on a checkerboard. Each minimum-length move takes you from black square to a white square or vice versa. Therefore, we can’t return to where we started after an odd number of moves. The second-shortest move has length $\sqrt{2}$, so the best we can do is:
Therefore, a lower bound for the length of the optimal walk is given by:

\[
\text{Lower Bound} = \begin{cases}
0 & \text{if }N = 1 \\
N & \text{if }N\text{ is even} \\
N-1+\sqrt{2} & \text{if }N\text{ is odd and }N \ge 3
\end{cases}
\]

Putting it all together

So in the end, the smallest possible ratio of bounds assuming there are at least two Pokéstops is given by:

$\displaystyle
\text{Bound Ratio} = \begin{cases}
2-\tfrac{2}{N} & \text{if }N\text{ is even} \\
2-\tfrac{2\sqrt{2}}{N-1+\sqrt{2}} & \text{if }N\text{ is odd}
\end{cases}
$

The smallest bound ratio that works for all $N$ is $2$, so this is the ratio we should use if we don’t know how many Pokéstops there are.

For the second part of the Riddle, we are given a very specific arrangement of Pokéstops: the set of points $1 \le i,j \le M$ such that $\mathrm{gcd}(i,j) = 1$ (greatest common divisor is $1$). The problem asks for $M=1000$, but we’ll keep $M$ as a parameter for now.

Upper bounds

Any tour that visits all the Pokéstop and returns to the starting point gives us an upper bound. With this many nodes, it’s impossible to check every tour, so we’ll compare different heuristics for choosing admissible paths and see how they compare.

Trivial upper bound: An obvious way to hit all the stops is to simply visit every point with integer coordinates in the $M\times M$ square. We know how to do this optimally from the first part of the problem; the optimal tour has length $M^2$ if $M$ is even and $M^2+\sqrt{2}-1$ if $M$ is odd. See the illustration below for example constructions:
So the trivial bound for the case of interest is 1,000,000. We can definitely do better!

Sierpiński bound: One way to find a reasonable tour is to use a space-filling curve, which maps every point in the square to a point on a curve. This gives us a way to order the stops based on where they lie on the curve. We then visit the stops in that order. This heuristic was pioneered by Prof. John Bartholdi III and others, and does very well in many cases.
The Sierpiński curve is often used here, and it’s what I used to find an upper bound. Here are some examples of solutions for different $M$ values.
These paths have lengths 313.9 and 1828.8, respectively. Using this method, our upper bound improves to 815,234 for the $M=1000$ case, and this was computed in 0.35 seconds.

Columnwise bound: The Sierpiński approach takes advantage of the pseudouniform distribution of points, but it doesn’t leverage the fact that points often appear in lines. For example, the rows and columns corresponding to prime coordinates are always full. Another heuristic, suggested by Diarmuid Early in a comment, is to proceed in a lawnmower-like pattern, but two columns at a time. So as we move up or down a pair of columns, we pick the next nearest point from the pair of available points at each step. Here are examples for the same grid sizes.
These paths are slightly shorter than the Sierpiński ones, with lengths of 308.3 and 1721.8, respectively. Using this method, our upper bound improves to 735,394 for the $M=1000$ case, and was computed in 2 seconds.

More on upper bounds: Other notable heuristics for upper-bounding TSP problems include the nearest neighbor algorithm and the Christofides algorithm. These don’t work well for our instance because they require computing all pairwise distances, a prohibitively expensive task when we have roughly 600,000 Pokéstops. The Sierpiński and columnwise algorithms have complexity $\mathcal{O}(n)$, where $n$ is the number of stops, whereas computing pairwise distances is $\mathcal{O}(n^2)$. This is a significant difference because $n$ is so large — if an $\mathcal{O}(n)$ algorithm takes 1 second then $\mathcal{O}(n^2)$ will take roughly 7 days!

Lower bounds

Trivial lower bound: One possibility is to count how many total stops there are, and assume we can find a path consisting entirely of adjacent stops. This isn’t possible of course, but it yields a lower bound. It’s relatively easy to write computer code to count this quantity, or we can use the fact that the density of stops in the $M \times M$ square approaches $6/\pi^2 \approx 0.6079$ as $M\to\infty$ (source). For the case $M=1000$, the lower bound turns out to be 608,383. Lots of room for improvement!

Averaging bound: Another observation, again courtesy of Diarmuid Early, is that each Pokéstop has two edges emanating from it. So if we assume each stop is connected to its two nearest stops, we will get another lower bound on the shortest possible path. Computing this quantity for the case $M=1000$, we obtain a much-improved 643,811.

Held-Karp relaxation: This final bounding method is significantly more advanced. Finding a set of edges (i.e. assigning each edge a label 0 or 1) that yields a valid tour requires two things:

1. each node has exactly two incident edges labeled 1
2. there are no disjoint cycles (it’s a connected path)

What makes this problem so hard is the second constraint. There are exponentially many cycles, so it’s not feasible to rule each one out. If we relax the problem by removing the disjoint cycles constraint, and allow the label on each edge to be any number between 0 and 1, the problem turns into a linear program (LP), which can be solved very efficiently. Successive refinements can then be made to improve the solution by ruling out particular cycles. This is known as the Held-Karp LP relaxation. Unfortunately, this still requires computing all pairwise distances, which we already decided was too costly (see above). The LP also has $\mathcal{O}(n^2)$ variables, since we need a variable for each edge. So I made two simplifying assumptions:

1. Each node may only be connected to one of its $k$ nearest neighbors. This is a relaxation to the GTSP, (traveling salesmsan problem on a graph). This means the number of variables, constraints, and distances we need to compute are now $\mathcal{O}(kn)$.
2. The final path will be symmetric ($x=y$). This allows us to use half as many variables and constraints and greatly speeds up computation.

To find an appropriate $k$, I solved the relaxed LP with $k$ values of 4, 8, 12, 16, 20. The solutions were 695251, 694956, 694954, 694952, 694952. So it seems there is no use in adding any more edges. For those that are interested, I implemented the solution in Julia using JuMP with Gurobi. On my laptop, the LPs took 30–90 seconds to solve.

Putting everything together

Here is a plot comparing all the bounds above.
So ultimately, our best bound for the case $M=1000$ is

\[
694952 \le L^\star \le 735394
\]

for an approximation ratio of about $1.06$.