Bridging the gaps with Street View
May 3rd, 2013 | Published in Uncategorized
Recently we sent our Street View cars driving through the historic seaport town of Kaliningrad (the modern name for Koenigsberg) 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 Koenigsberg.
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.
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 Koeningsberg 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.
In other words, leave the mathematics to the mathematicians and just enjoy the scenery with Street View!
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:
While the bridges of Koeningsberg 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.
View Larger Map
Today, it’s traditional for newly married couples to hang engraved padlocks on one of the original seven bridges of Koenigsberg
In other words, leave the mathematics to the mathematicians and just enjoy the scenery with Street View!