Take the 2-minute tour ×
Geographic Information Systems Stack Exchange is a question and answer site for cartographers, geographers and GIS professionals. It's 100% free, no registration required.

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!

share|improve this question
19  
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
7  
Wait, since when do only Christian kids get Santa visits? –  Steve Bennett Dec 24 '12 at 0: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 2: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 8:49
3  
So. First step is to gather a dataset for all dwelling locations for the World. Anyone care to post a dropbox link? –  Simon Dec 24 '12 at 14:11
show 8 more comments

5 Answers 5

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

share|improve this answer
add comment

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.

share|improve this answer
1  
In case you don't believe in the helpers, here's the proof: en.wikipedia.org/wiki/Prep_%26_Landing –  Tobias Kienzler Dec 30 '13 at 10:46
add comment

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. Merry christmas and a happy new year for all the awesome people at stackexchange :). I'v

share|improve this answer
3  
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
add comment

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/

share|improve this answer
add comment

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

share|improve this answer
    
If your in the air you would surely have to take into consideration the roundness of the earth and your altitude. –  Natrix Jan 3 '13 at 18:51
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.