52

I'm new to GIS.

I need some help in determining the best or most efficient route, using a flying sleigh, through all the houses in the world. One of my coworkers told me that this site would be the best place to ask, because I would find lots of helpful GIS experts.

I will need some guidance about what software to use, where to get the data, and how to process it. Since I had some extra expenses this month, I would prefer some Open Source solutions.

Thank you all!

PS: I'm in a bit of a hurry, as I need this for tomorrow!

blah238
  • 35,793
  • 7
  • 94
  • 195
Santa Claus
  • 545
  • 4
  • 4
  • Related: One dimensional map of the world? – blah238 Dec 23 '12 at 20:18
  • 1
    If you can simplify the problem size down to "all cities in the world", @utunga's answer in the above question should get you pretty close, and you might even get it done in time! :) – blah238 Dec 23 '12 at 20:32
  • 20
    This is basically Travelling Salesman Problem which unless you're willing to use a heuristic has n! complexity so good luck finding any solution for that many n before the universe ends... – smalltown2k Dec 23 '12 at 21:33
  • 1
    Could you use some kind of parallel approach here. Instead of working through every house in sequence, start up some (elven?) worker processes and hand-off a clustered subset of the houses? Of course, we'd still need to determine the best clustering approach... – BradHards Dec 23 '12 at 21:46
  • Good news! You won't need to get to every house on the planet. Since you only need to visit christian children, there are only ( 15% christian out of 2 billion children, appr. 3,5 children per household) roughly 100 million houses you will have to visit. – GR_ Dec 23 '12 at 21:51
  • 7
    Wait, since when do only Christian kids get Santa visits? – Steve Bennett Dec 24 '12 at 00:10
  • 4
    Let us just assume that Mr. Claus has a list of housesholds to visit and keep it non-denominational. Thanks :) – blah238 Dec 24 '12 at 02:41
  • 9
    Is this route also constrained to start at the North pole? North geographic pole, or north magnetic pole? – Spacedman Dec 24 '12 at 08:49
  • 3
    So. First step is to gather a dataset for all dwelling locations for the World. Anyone care to post a dropbox link? – jakc Dec 24 '12 at 14:11
  • 1
    @Spacedman Wikipedia says geographic north pole. :D – Green Noob Dec 24 '12 at 16:09
  • 1
    Looks like he already figured it out: http://www.google.com/santatracker/ – lynxlynxlynx Dec 24 '12 at 18:14
  • @Smalltown2k This gives a value for n: http://www.telegraph.co.uk/topics/christmas/6859529/Father-Christmass-Christmas-Eve-in-figures.html "There are roughly 2 billion children worldwide. However, assuming Santa doesn't visit the children of Hindu, Muslim, Jewish, atheist and so on parents, that leaves the 35 per cent or thereabouts whose parents consider themselves Christian. That's still an impressive 700,000,000 children in a night. Assuming three children per household, that's 233,000,000 stops for Santa and his sleigh." – Harry Wood Dec 29 '12 at 22:32
  • ;) by the time you would end the exact calculation with any known algorithm there would be milions of new houses to count in. good luck and try to notify us with your result Edit: try to ask santa - http://www.santabot.com/ – Dario Filipović Dec 24 '12 at 16:33

5 Answers5

25

Hang on surely Rudolph knows where to go. He's been doing it for years.

Andrew
  • 251
  • 2
  • 2
16

Often it is good to address the need that is stated rather than answering the question that was asked. I would like only to point out that there is a well-known parallel solution that neatly circumvents all the technical computing issues: Santa has helpers. These agents work asynchronously and independently to identify the houses that need visits and carry out the deliveries. No special GIS computation on Santa's part is needed.

It is wonderful that this technology scales, so that as the world's (Christian) population has expanded by several orders of magnitude over the millennia, Santa's ability to carry out his duties has never seriously been in doubt: the number of available helpers has grown in direct proportion to the number of houses that need visits.

There is a physical demonstration of the existence of these helpers. If, to assume the contrary, just one individual tried to deliver gifts to, say, one billion dwellings throughout the course of a calendar day (which spans 48 hours, accounting for time zones), they would have to visit almost 6000 dwellings per second. A lower bound for the mean distance between dwellings is afforded by the density of the world's larger cities, in which people may live only 10 meters or so apart. This would require an average speed of 6000 * 10 = 60,000 meters per second, far surpassing the sound barrier (creating sonic booms that are not heard on Christmas) and creating so much atmospheric friction that the sleigh would become a blazing fireball destroying everything in its proximity. Although this gives us a new understanding of the origin of the red glow in Rudolph's nose, it clearly demonstrates that only a parallel solution is even possible, QED.

whuber
  • 69,783
  • 15
  • 186
  • 281
6

This is something you can probably solve by using the Warshal's or Dijkstra's algorithm

Although the number of houses in the world is way too big it would take a long time to compute that, I think this is a good initial point. Now I don't have the time to explain them but i give you an initial point. I'll go out with my family now and maybe I'll go back to this question the next year.

Fezter
  • 21,867
  • 11
  • 68
  • 123
Roger
  • 161
  • 3
  • 4
    Thank you for the kind words. But: (1) How would either of those algorithms solve this traveling salesman problem? (2) Dijkstra's algorithm (to find shortest paths between two given points in a given network) is fast. Applying it to a dataset of all dwellings in the world, if it were suitably pruned to include edges only to several nearest neighbors of each dwelling, would not only be feasible, but reasonably quick--probably needing only seconds or minutes of computation. – whuber Dec 24 '12 at 17:43
2

Looks like Google figured it out for you already, Santa! In fact, you're supposed to be in Asia at the moment!

http://www.google.com/santatracker/

Matt
  • 957
  • 1
  • 6
  • 14
0

With a dataset containing the latitude and longitude of every dwelling (census data?), I'd maybe use the Haversine formula in one programming language or another. But then again, I'm not an elf.

Haversine Formula

AIRAD LABS
  • 1
  • 2