Friday, May 3, 2013

[G] Bridging the gaps with Street View

| More

Google Lat Long: Bridging the gaps with Street View

Recently we sent our Street View cars driving through the historic seaport town of Kaliningrad (the modern name for Königsberg) in Russia as part of our quest to keep Google Maps comprehensive, accurate and useful. While there, we were reminded of a classic mathematical problem: the Seven Bridges of Königsberg.

The mathematical problem posed an interesting challenge: find a route through Kaliningrad—which was once separated by the Pregel River—by crossing each of the seven bridges in town. The catch? One could only cross each bridge exactly once.

This sketch shows the town’s original seven bridges in green (Source: Wikipedia)

In 1735, Leonhard Euler, one of the most prolific mathematicians of all time and our recent Doodle subject, concluded that there was no solution to the problem because it was impossible to find a route that would cross each bridge only once. This famous problem and Leonhard Euler’s non-resolution paved the way for important discoveries in the field of mathematics including graph theory and topology.

Fast forward 278 years to today where we still rely on Euler’s findings to calculate optimal driving routes for our Street View cars. We use sophisticated algorithms, based on graph theory, to determine the best route through a city or town—helping us capture all the images we need in the shortest amount of time. Though these algorithms are complex, in simple terms, it's equivalent to solving the problem of drawing a house without lifting your pen and never going over the same segment twice. Like this:

(Source: Vincent Furnon, Google Operations Research Team)

While the bridges of Königsberg may be one of Kaliningrad’s most famous landmarks, you can also explore other parts of this historic town with Street View—including the oldest building in the city, the Juditten Church, which was built before 1288, and King’s Gate, one of the city’s original six gates built during the 19th century.

Today, it’s traditional for newly married couples to hang engraved padlocks on one of the original seven bridges of Königsberg - View Larger Map 

In other words, leave the mathematics to the mathematicians and just enjoy the scenery with Street View!

Posted by Daniele Rizzetto, Operations Manager, Street View

No comments: