Iain Duncan

In our first discussion of the Travelling Salesman Problem (TSP) and Santa’s yearly journey, we talked about the problems he experiences when planning his route and some of the ways he may go about dealing with them. However, as much as I hope that article was satisfying and complete in its own right, we have left one very important question unanswered: how fast does Santa Claus fly? 

Sadly, we will never know his exact path. We have neither the location information nor the computing power needed to work it out for ourselves and Santa refuses to release the list for privacy reasons. Fortunately, we don’t need to know his exact path to work out his speed. In addition to working on ways to solve the TSP, research has also been done on how to estimate how long the shortest path will be. We expect this path to involve two important numbers. The number of nodes, n, and the area over which those nodes are distributed, A. 

Before I just present you with results, let’s see if we can make a guess what form the equation relating the path length to A and n will take. The first thing we might realise is that the path will consist of n links between pairs of nodes. The second is that, when more points are added to the same area, the average distance between two nodes decreases. The only question is, how do these two relationships interact? The insight comes when we consider the relationship between the average density of nodes and the average distance between points. Let’s look at eight randomly distributed points in a given area as an example:

The average density of nodes is the total number of nodes (8) divided by the total area (100), so rho = n/A = 8/100 = 0.08. This density is, at its heart, an answer to the question ‘how many nodes are there in some bit of area?’, which is very similar to another question ‘how much area does a given node occupy?’.

In the diagram above, each of the shaded polygons represents the area which is closest to a given node. The average area of these polygons is the answer to the second question and it happens to be given by a = 1/rho = A/n = 100/8 = 12.5. Now that we have an area associated with an average node, we can get a length by taking the square root of that area, which turns out to be proportional to the average distance between randomly distributed nodes in an area A. So, in our example, we get l ~ sqrt(12.5) = 3.5.

Basically, what this all means is that for a route containing n line segments, each of them will have an average length proportional to sqrt(A/n). We therefore multiply the average segment length by the number of segments to get an equation for the average minimum path length: L = b*sqrt(An), where b is some number we don’t know for sure. We can’t mathematically prove what b is, but we can run a large number of computer simulations and measure the shortest path length in each of them. Analysis of these lengths yield the final equation: L = 0.88 sqrt(An). This will be an invaluable tool in finding Santa’s speed. 

As before, we know Father Christmas must visit about 900 million households, so we can set n = 900,000,000. The surface area of the Earth is 510 million square kilometres, so this will be our value for A. Performing the calculations, we find that Santa’s journey is 600 million km long and that he travels at an average speed of 7 million m/s – roughly 20,000 times the speed of sound and 3% the speed of light! 

And that is where this story should end, on a nice, definite result. It doesn’t. We have made a couple of assumptions which aren’t necessarily true. Firstly, we should note that b was only worked out for a flat surface and the earth is in fact, round. I could not find an example of someone working out b for a sphere, so we may expect some difference in this value when applied to Santa’s journey. However, b is relatively insignificant compared to the number of houses and area involved, so our use of 0.88 should produce a result which is still quite close to the actual result. The next assumption was that the houses Santa needed to visit were randomly distributed. This is definitely not true. Almost nobody lives in the ocean and land only makes up for 30% of the Earth’s surface. On the land, people live together in towns and cities. There is very little randomness in the location of human settlements. We have already noted that the average path length decreases as the area gets smaller, so we expect people clustering together in cities to reduce the total length and therefore speed, possibly by quite a lot. However, when we take into account the time Santa spends in each house delivering presents and eating cookies, it seems reasonable that the sleigh does, in fact, travel at 3% the speed of light.