Directions Magazine
Hello. Login | Register

Press Releases

Home | Submit Press Release

Math Makes Mobile Maps Meaningful

Bookmark and Share
Thursday, May 8th 2014
| Karlsruhe, Germany
Read More About: cartography, gnss, labeling, navigation


Math Makes Mobile Maps Meaningful

KIT in the Science Year “The Digital Society:” Mathematics and Theoretical Computer Science Help Optimally Represent Information on Navigation Systems

 

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 digital maps, 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 everyday life 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.”

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.

Science Year 2014

Communication, energy supply, mobility, industry, health care, leisure time: Digital technologies have long been part of our everyday life, they open up new opportunities and offer solutions for problems of society. At the same time, they pose challenges. Opportunities and risks will be in the focus of the Science Year 2014 – The Digital Society. At the KIT, researchers of all disciplines study various – technical and societal – aspects of digitization. The digital press kit of KIT relating to the Science Year 2014 contains short portraits, press releases, and videos:
http://www.pkm.kit.edu/digitalegesellschaft 

About Karlsruhe Institute of Technology (KIT)

Karlsruhe Institute of Technology (KIT) is a public corporation according to the legislation of the state of Baden-Württemberg. It fulfills the mission of a university and the mission of a national research center of the Helmholtz Association. Research activities focus on energy, the natural and built environment as well as on society and technology and cover the whole range extending from fundamental aspects to application. With about 9000 employees, including nearly 6000 staff members in the science and education sector, and 24000 students, KIT is one of the biggest research and education institutions in Europe. Work of KIT is based on the knowledge triangle of research, teaching, and innovation.

Image: Overfull maps on the satnav or the smartphone display can be prevented with the help of mathematically based algorithms. (Photo: KIT / Nöllenburg)

Bookmark and Share

Stay Connected

Twitter RSS Facebook LinkedIn Delicious Apple Devices Android Blackberry






Recent Comments

Recommendations And Report Of The Stimson Task Force On US Drone Policy

The Top Five Things You Need to Know about Drones and GIS
A Glossary of Unmanned Aerial Vehicle (UAV) Terms
Don’t Miss These Resources on Unmanned Aerial Vehicles (UAV)
Mapping Disaster: A Global Community Helps from Space
Alteryx 9.0: “Data Scientists Not Required!”
Millennium Space Seeks Your Space-enabled Big Ideas
Using Other People’s Maps and Data: Let’s Keep it Legal
The Present and Future of CartoDB

DirectionsMag.com

About Us | Advertise | Contact Us | Web Terms & Conditions | Privacy Policy
© 2014 Directions Media. All Rights Reserved