The Traveling Salesman Problem (TSP) is a classic computer science challenge: What path do you choose when visiting a set of destinations so as to minimize the distance traveled? It’s a problem for which there aren’t any easy shortcuts or a quick formula, and hence it’s become something of a cause célèbre among mathematicians and programmers for measuring the efficiency of algorithms and the processing speed of grid computers.

One of the most impressive recent TSP calculations minimized the distance traveled between Swedish towns — all 24,978 of them(!). I was hoping to overlay the map of the shortest route onto Google Earth, but the projection isn’t right. The raw data is available, so I might well turn it into a KML file sometime.

In the meantime, though, I wanted to make my own TSP solver for KML files of placemarks.

Here it is.

Instructions: Collect up to nine placemarks in a folder. (Hint, you can also right-click on city icons and save them as placemarks.) Right-click on the folder and Save it locally as a KML file (NOT as a KMZ file). Use the TSP Solver to upload the file and wait around 10 seconds. You’ll get a KML file back that contains the shortest route between those placemarks. Guaranteed:-)

Unfortunately, This being a PHP script running on a server, nine placemarks is all that the algorithm can manage in a reasonable time. Ten placemarks would take 10 times longer. The current algorithm isn’t very efficient, in any case, and I’ll be playing with better solutions in the coming weeks, but I just wanted to get a base system working now. Any speed suggestions are most welcome, or else feel free to roll your own, better TSP solver.

• This morning, Agent Earth (beta) worked fine: Throw a US zip code or address at it and out comes KML file containing all the real estate for rent or for sale on Google Base. In other words, it’s a Google Base – Google Earth mashup, wrapped in a nice package. Tonight, though, I couldn’t get it to work. Try your luck.
• The Frick Collection ranks among my absolute favorite museums. Now a significant portion of its art has been georeferenced down to the specific room by LuciaM on Google Earth Community, with an image and further links for each painting. Love it…
• Rockit is an Italian music site that has georeferenced scores of music places in Italy. Some of them that I know definitely match up. I only wish the venues would be updated with live info, but failing of that, many of the placemarks have links to websites where you can get such details.

An update on the reported blocking on Google Earth’s servers in Morocco. Two further news items have surfaced that appear to confirm multiple user reports of Google Earth’s servers being inaccessible from as long ago as August 14.

That, at least, is what Maroc IT reports, in an article pretty much parrotted by France’s PC Inpact. The only problem is that both articles manage to get pretty much every other fact wrong. No, India, Israel and South Korea have not blocked access to Google Earth, only Bahrain. No, the US government has not “insisted” that Google Earth censor the White House and, where-do-they-get-this-from, large parts of Manhattan.

Best to head for the hard-core local bloggers then. Temps Libres has a blow-by-blow account of attempts to connect, and manages to localize the problem. As of yesterday, at least one provider — Maroc Télécom — has unblocked Google Earth’s servers. Temps Libres puts it succinctly:

La question qui se pose maintenant est, était ce vraiment de la censure ou bien un simple probléme technique ?, peut être qu’on ne saura jamais!

(“The question now is, was it really censorship or a simple technical problem? Perhaps we’ll never know!”)

What I really love about the censorship debates around Google Earth is that — unlike other content deemed subversive online — Google Earth can only ever be faulted for portraying reality accurately. There are no incitements to violence, nor tendentious arguments, no blasphemies, no racist or bigoted polemics, no slander, no hate speech… Just images. Governments wanting to repress access to the information in Google Earth’s databases cannot credibly justify doing so with the usual pretext of protecting the populace from moral turpitude — which didn’t stop Bahrain from trying, BTW.

Instead, arguments in favor of governmental hobbling of Google Earth have to raise the specter of public security — except that many other commonplace tools are far more dangerous, starting with cars, cell phones, GPS units, paper maps, digital cameras, laptops, the Internet itself, wire transfers… Worst of all, government bans on Google Earth merely blind the locals — everyone else is still all-seeing.

When Windows Origami was but a twinkle in the rumormonger’s eye, we here at Ogle Earth (and by we, we mean I) speculated on its possible use as a portable Google Earth with live positioning via GPS. Not six months later, enter JGUI’s GPS.RADAR, available now for download as a freeware beta.

Of course, none of us (and by us, we mean I) actually have an ultra-mobile PC (UMPC), but it’s programs like GPS.RADAR that begin to make Origamis interesting. (Via ZDNet’s The Mobile Gadgeteer)

Integrating online collaborative spreadsheets over on EditGrid with Google Earth (and much else besides) continues to get quite a few people excited. Digital Geography, for example, latches on immediately to the educational opportunities this this combo affords.

Meanhwhile, EditGrid’s developers have released add-ons, including Grid2Map, which converts spreadsheets with postal addresses to Google Maps via a simple wizard.

But the most interesting development is the collaboration between Valery Hronusov and EditGrid’s Alan Tam, here on the EditGrid user forum. Alan’s point is this:

Thanks for all your brillant effort trying to use Deep Permalink to generate KML files. We in EditGrid, however, think that this solution, although works, is a sub-optimal way to let user manage their data.

In Beta 10, we have released a feature allowing exporting the whole spreadsheet into an XML file. This XML file can be optionally passed through an XSL Transformation to form another XML or text file.

That really amazing, especially as Alan comes up with an example for Valery’s data:

• Here is Valery’s spreadsheet.
• Here it is as XML.
• Here is the XSL that transforms that to KML.
• Here is the resultant KML file.
• And here it is in Google Maps.

Just like magic.

[Update 2006-08-24 00:11 UCT: Forgot the punchline: Because the XML is updated automatically as you change the spreadsheet, so is the KML. It’s therefore worthwhile to subscribe to the KML via a network link, to keep it dynamic.]

• This is the second mention in blogs, but I haven’t seen it confirmed by a news service: Apparently, Google Earth’s servers are inaccessible in Morocco. (Either that or somebody had trouble connecting and before you know it, a meme is born.) Can anybody in Morocco confirm or deny this story?
• Oracle publishes a detailed technical article by mappinghacks.com‘s Rich Gibson on how to Build a Google Earth Interface on Oracle Database XE. The examples use PHP. (Via Arun’s Blog)
• Le Blogue du LFG finds another remarkable KML resource: Methalithic portal’s online database of over 15,000 prehistoric monuments is now online.

For my own reference, now:

• James Fee is right. Loc.alize.us‘s Flickr geotagging bookmarklet is the easiest way to georeference one’s photos. Once they’re in there, view them in Google Earth thus.
• Geody is a very interesting geosearch portal. Unique feature: Look up stuff on the moon and other planets. back on Earth, search results come linked to Google Earth, NASA World Wind, etc…

Another nifty way of visualizing scientific data: Deep-Sea News (gotta love them niche blogs) reports that over 3,500 dives by the Alvin submarine (star of many a National Geographic Special) are now mapped to KML as part of the Marine Geoscience Data System (MGDS) project.

Deep-Sea News has the lowdown on the Alvin dives. in the meantime, I went trawling through the geodata directories of MGDS, and found many more interesting KML files. For example:

• High resolution maps of the ocean floor of the Pacific, as mapped by Alvin.
• An awesome KML file with the names of thousands of ocean floor geographic features. It’s like Geonames.org for underwater geography.
• Huge high resolution maps of the Indian Ocean (not for the faint of CPU).
• Thousands of sediment cores, georeferenced to their database entries online.
• The Earth’s tectonic plates and boundaries. (Nice one)

  

• Several hundred georeferenced photos of the seabed, as if Alvin had a Flickr account (and why wouldn’t it?).

  

I’m just exhausted from exploring this treasure trove. Go do your own digging here. (it’s OK, MGDS links to it from the home page.) It definitely makes you wish for the promised bathymetry data in Google Earth.