Zoomless Maps: Models and Algorithms for the Exploration of Dense Maps with a Fixed Scale

• Applicant: Professor Dr.-Ing. Jan-Henrik Haunert
• Subject Area: Geodesy, Photogrammetry, Remote Sensing, Geoinformatics, Cartography
• Term: from 2018 to 2023
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 408056693

• Final Report Year: 2023

Final Report Abstract

We have focused on developing models and algorithms for the presentation of large collections of point features on mobile devices. In particular, we have addressed the limitations of established zoomand-pan interfaces and presented alternative strategies that enable the exploration of all information through novel interaction capabilities. We have presented different flexible models which place labels either directly onto their point features or at the boundary of the map. Each of our models presents only a subset of all features at any given time. Instead of relying only on zooming and panning, each model implements one specific interaction technique that allows the user to access all the information. Specifically, a user can browse through the information by navigating through different pages, sliding a strip of labels, or clicking through multiple stacks of labels. Considering established cartographic criteria and principles from information visualization, we formalized specific optimization problems. For most problems, we were able to prove that they are NP-hard, and thus developed approaches employing integer linear programming and heuristics. For the non NP-hard problems we have provided efficient exact algorithms. Particular emphasis was on the quality of the results. We evaluated each model quantitatively by assessing the quality of the solutions with respect to the mathematically defined criteria. For our heuristic solutions, we compared their quality in terms of the optimized criteria with that of optimal results. We have shown that our algorithms are suitable for applications in real-time systems and produce high-quality results. In addition to the quantitative analysis, we took up the concept of user-centered design and assessed the usability and utility of our models in an empirical study. We implemented three of our models as interfaces in a desktop environment and compared them against an established zoom-andpan interface in a comprehensive online study. Assessing different quantitative measurements as well as the participants’ ratings and comments, we were able to show that the tested zoomless interfaces support users when exploring the map. Compared to a zoom-and-pan interface, we proved that the use of these particular interfaces • significantly reduces the number of zooming and panning operations, • improves the accuracy, • allows a larger map area and more context to be visualized,when searching for specific information. To summarize, we have developed novel models and algorithms for presenting large collections of point features on mobile devices. Instead of solely relying on standard interactions like zooming and panning, our strategies implement specialized interaction techniques for browsing through the information. Comprehensive evaluations have confirmed both that our results are of high quality and that our interaction techniques are useful and user-friendly.

Publications

• Multi-page Labeling of Small-screen Maps with a Graph-coloring Approach. Advances in Cartography and GIScience of the ICA, 2, 1-8.
  Gedicke, Sven; Niedermann, Benjamin & Haunert, Jan-Henrik
  
• Point feature label placement for multi-page maps on small-screen devices. Computers & Graphics, 100, 66-80.
  Gedicke, Sven; Jabrayilov, Adalat; Niedermann, Benjamin; Mutzel, Petra & Haunert, Jan-Henrik
  
• Zoomless Maps: External Labeling Methods for the Interactive Exploration of Dense Point Sets at a Fixed Map Scale. IEEE Transactions on Visualization and Computer Graphics, 27(2), 1247-1256.
  Gedicke, Sven; Bonerath, Annika; Niedermann, Benjamin & Haunert, Jan-Henrik
  
• Exploring Spatio-Temporal Event Data on a Smart Watch. Abstracts of the ICA, 5, 1-2.
  Bonerath, Annika; Temerowski, Lukas; Gedicke, Sven & Haunert, Jan-Henrik
  
• An Empirical Study on Interfaces for Presenting Large Sets of Point Features in Mobile Maps. The Cartographic Journal, 60(1), 25-42.
  Gedicke, Sven & Haunert, Jan-Henrik
  
• Ein Algorithmus zur automatischen Platzierung taktischer Zeichen in der digitalen Lageskizze. Zeitschrift für Forschung und Technik im Brandschutz vfdb, 72(2):59–65, 2023.
  Sven Gedicke, Lukas Arzoumanidis & Jan-Henrik Haunert