Beyond Zooming: Models and Algorithms for Mobile Maps with Extended Interaction Techniques

This thesis focuses on the development and evaluation of novel interfaces for the presentation of large and detailed geographic data sets on mobile devices. Especially when the density of information is high, a major challenge emerges due to the constrained screen space, making it difficult to maintain uncluttered map representations. Established interfaces rely on not showing all information simultaneously and providing basic interaction capabilities such as zooming and panning for further diving into a map's details. However, to thoroughly explore the information in an area of interest, such zoom-and-pan strategies often require a user to zoom in to a very large scale. To retain the spatial context, the user has to repeatedly zoom and pan the map section. Not only can this process be tedious, but the changes in scale and level of detail also impede the cognitive linking of successive visualizations. <br> Addressing this issue, the thesis follows the premise that advancing beyond common zoom-and-pan methods is possible by shifting attention towards specialized interaction techniques. In this context, <em>zoomless maps</em> will be introduced. Such maps implement advanced interaction capabilities, which enable users to explore all available information without the need for zooming or panning, thus maintaining the map scale and spatial context unchanged. These novel interactions can also complement traditional zoom-and-pan techniques, broadening the capabilities of established map interfaces. <br> In particular, different variants of <em>zoomless maps</em> will be developed, each implementing a distinct interaction technique. The implementations rely on mathematical models that consider multiple criteria tailored to a corresponding interaction. A criterion is either optimized or enforced as a constraint within a mathematical optimization problem. Taking into account the computational complexity of a problem, suitable optimization methods are applied, with a primary focus on combinatorial optimization. <br> Exact methods, such as integer linear programming, will be introduced, which provide mathematically optimal solutions. These solutions enable the verification of the mathematical models using different quality metrics. Through the comparison with optimal solutions of specialized models -- each optimizing only one criterion at a time -- it will be shown that the multi-criteria models allow for a satisfactory trade-off across all considered criteria. However, since exact methods may prove to be too slow for interactive scenarios, heuristics will be presented that rather focus on efficiency than on optimality. Still, using the optimal results of exact methods as benchmarks, it will be shown that the heuristics yield high-quality solutions with regard to the optimized objectives. <br> Beyond quantitatively evaluating the developed models and algorithms, one key objective of this thesis is to verify the usability and utility of <em>zoomless maps</em> and to prove their merits over established zoom-and-pan strategies. To that end, a comprehensive empirical user study will be presented that compares three variants of <em>zoomless maps</em> against a standard zoom-and-pan interface. For the common task of browsing through a large collection of features to find an object that suits a user's preferences best, it will be shown that the use of <em>zoomless maps</em> has a positive impact on accuracy in terms of the given search criteria. Additionally, it reduces the number of performed zooming and panning operations and leads to a smaller scale with more map context being available when selecting an object. <br> The exploration of ways to validate a broader generalizability of the benefits of <em>zoomless maps</em> as well as possible development potentials are outlined as part of future research.