Math makes mobile maps meaningful

May 8, 2014 by Monika Landgraf
Overfull maps on the satnav or the smartphone display can be prevented with the help of mathematically based algorithms. Credit: KIT / Nöllenburg

Due to the success of navigation devices and smartphones, digital maps are used widely in everyday life. They guide us safely along motorways or to the next bakery as long as the map is good and clear. However, representation of many information items on small, mobile screens is not trivial. At the Karlsruhe Institute of Technology (KIT), computer scientists have now developed a method to ensure mathematically optimal adaptation of the labeling to the perspective and driving direction.

"Digital maps are often superior to paper maps," Martin Nöllenburg, KIT, explains. "Digital maps can be rotated or zoomed. Places of interest can be added by a thematic selection from databases." The challenge, however, consists in keeping the representation and labeling clear, no matter how the user adjusts the visible range and how the route continues. "When the labelings overlap, jump or flicker, the added value is lost and a driver distracted by irritating representations may be a danger in road traffic."

At the KIT, Nöllenburg heads a group of young researchers, which focuses on mathematically exact geovisualization, i.e. the representation of information in maps. This research area is of interest not only for mathematicians and theoretical computer scientists. This is reflected by the fact that Nöllenburg was granted a research award by the Google Internet and Maps Service. "In the end, usable algorithms can only be programmed, if the problem is understood mathematically," Nöllenburg says.

By means of the mathematical description of , the difficulty of the problem can be estimated first. For example, maximization of the number of labelings in the selected image section of the navigation device along a route is one of the mathematical problems, the so-called NP-complete problems, that require most of the computing time. "When increasing the number of objects in the map, the required computing capacity grows exponentially," Nöllenburg emphasizes. "And computing capacity quickly reaches its limits, especially on mobile devices."

Together with his team, Nöllenburg develops algorithms of higher performance due to a reasonable limitation of the general problem. "Instead of trying to maximize the number of displayed labelings, a good compromise of legibility, computing time, and information depth is reached by keeping the number of labelings in the given section constant," Benjamin Niedermann explains. He developed the mathematical proofs. "In any case, man cannot sensibly perceive more than three to seven objects." On this basis, it is not only possible to find a simple method for the sensible labeling of a map. It can also be shown that the computing time of the new method rises moderately only when the object number is increased. "Interestingly, limitation of optimization on a section of the map causes the sum of labelings to increase along the complete route. Hence, more places of interests are mentioned along a way."

"The more mobile end devices are used in everyday life, the better should be the mathematical basis," Nöllenburg says. "This is the only way to develop products that really support us in and do not require more time and effort for operation." Now, Nöllenburg and his team want to proceed from fundamental research to application and convert the mathematical methods into implementable algorithms. "I am sure that our methods will prove their value in practice."

Explore further: Google Maps update: Good lanes and last trains

More information: Andreas Gemsa, Benjamin Niedermann, and Martin Nöllenburg. Trajectory-based dynamic map labeling. In: International Symposium on Algorithms and Computation (ISAAC'13), pp. 413–423. Springer-Verlag, LNCS 8283, December 2013.

Related Stories

Google Maps update: Good lanes and last trains

May 7, 2014

According to Google, its Google Maps is the largest mapping site in the world. As of Tuesday, the mega-finder can be used as a souped-up personal assistant that anyone with a mobile device can appreciate whether on the highway ...

Drivers may use smartphones for maps: court

February 28, 2014

A California appeals court has tossed out a fine for a driver checking a smartphone map to escape traffic, offering a new interpretation in the crackdown on "distracted driving."

Google ditches location-sharing feature in map apps

July 10, 2013

Google on Wednesday released an upgraded version of its popular maps app for Android-powered smartphones and tablets that ditches a Latitude feature that let people share locations with family or friends.

Recommended for you

Your (social media) votes matter

January 24, 2017

When Tim Weninger conducted two large-scale experiments on Reddit - otherwise known as "the front page of the internet" - back in 2014, the goal was to better understand the ripple effects of malicious voting behavior and ...

Protective wear inspired by fish scales

January 24, 2017

They started with striped bass. Over a two-year period the researchers went through about 50 bass, puncturing or fracturing hundreds of fish scales under the microscope, to try to understand their properties and mechanics ...

'Droneboarding' takes off in Latvia

January 22, 2017

Skirted on all sides by snow-clad pine forests, Latvia's remote Lake Ninieris would be the perfect picture of winter tranquility—were it not for the huge drone buzzing like a swarm of angry bees as it zooms above the solid ...

Singapore 2G switchoff highlights digital divide

January 22, 2017

When Singapore pulls the plug on its 2G mobile phone network this year, thousands of people could be stuck without a signal—digital have-nots left behind by the relentless march of technology.

Making AI systems that see the world as humans do

January 19, 2017

A Northwestern University team developed a new computational model that performs at human levels on a standard intelligence test. This work is an important step toward making artificial intelligence systems that see and understand ...

0 comments

Please sign in to add a comment. Registration is free, and takes less than a minute. Read more

Click here to reset your password.
Sign in to get notified via email when new comments are made.