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

Abstract

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.

Diese Arbeit konzentriert sich auf die Entwicklung neuartiger Kartenanwendungen zur Darstellung großer geografischer Datensätze auf mobilen Geräten. Insbesondere bei einer hohen Informationsdichte stellt der begrenzte Platz auf dem Bildschirm eine Herausforderung dar, die eine übersichtliche Kartendarstellung erschwert. Etablierte Anwendungen zeigen nicht alle Informationen gleichzeitig an und ermöglichen es durch Interaktionen wie Zoomen und Verschieben, tiefer in die Details einer Karte einzutauchen. Um die Informationen in einem bestimmten Bereich umfänglich erkunden zu können, erfordern solche Strategien allerdings oft ein Heranzoomen auf einen sehr großen Maßstab. Um dabei den räumlichen Kontext nicht zu verlieren, muss wiederholt gezoomt und der Kartenausschnitt verschoben werden. Dieser Prozess ist mühsam und erschwert die Orientierung innerhalb der Karte. <br /> In dieser Arbeit wird diese Problematik aufgegriffen und mit <em>Zoomless Maps</em> ein alternativer Ansatz vorgestellt. Durch neuartige Interaktionsmöglichkeiten erlauben diese Karten eine umfängliche Informationserkundung, ohne den Maßstab ändern zu müssen. Die neuen Interaktionen können herkömmliche Zoom-und-Verschiebe-Techniken ergänzen und somit die Funktionen etablierter Kartenanwendungen erweitern. <br /> Es werden verschiedene Varianten von <em>Zoomless Maps</em> entwickelt, wobei jede eine unterschiedliche Interaktionstechnik umsetzt. Die Implementierungen beruhen auf mathematischen Modellen, die mehrere auf die jeweilige Interaktion zugeschnittene Kriterien berücksichtigen. Ein Kriterium wird entweder optimiert oder als Bedingung innerhalb eines mathematischen Optimierungsproblems gefordert. Unter Berücksichtigung der Komplexität eines Problems werden geeignete Optimierungsmethoden angewendet, wobei der algorithmische Fokus auf kombinatorischer Optimierung liegt. <br /> Es werden exakte Verfahren vorgestellt, die mathematisch optimale Lösungen liefern. Diese Lösungen ermöglichen die Überprüfung der mathematischen Modelle unter Verwendung verschiedener Qualitätsmetriken. Durch den Vergleich mit optimalen Lösungen spezieller Modelle, die jeweils nur ein Kriterium gleichzeitig optimieren, kann gezeigt werden, dass die multikriteriellen Modelle einen zufriedenstellenden Kompromiss zwischen allen betrachteten Kriterien ermöglichen. Da exakte Methoden für interaktive Szenarien jedoch oft zu langsam sind, werden zudem effiziente Heuristiken vorgestellt. Durch den Vergleich mit optimalen Ergebnissen der exakten Methoden wird gezeigt, dass die entwickelten Heuristiken neben einer schnellen Laufzeit qualitativ hochwertige Lösungen hinsichtlich der optimierten Ziele erreichen. <br /> Über die quantitative Bewertung der entwickelten Modelle und Algorithmen hinaus ist ein wichtiges Ziel dieser Arbeit, die Nützlichkeit und Benutzerfreundlichkeit von <em>Zoomless Maps</em> zu überprüfen und ihre Vorzüge gegenüber etablierten Anwendungen nachzuweisen. Hierzu wird eine empirische Nutzerstudie präsentiert, die drei Varianten von <em>Zoomless Maps</em> gegen eine Standard-Zoom-und-Verschiebe-Karte vergleicht. Für die Suche nach einem Objekt, das festgelegten Kriterien am besten entspricht, wird gezeigt, dass sich die Verwendung von <em>Zoomless Maps</em> positiv auf die Genauigkeit in Bezug auf die gegebenen Suchkriterien auswirkt. Darüber hinaus reduziert sie die Anzahl der durchgeführten Zoom- und Verschiebevorgänge und führt dazu, dass bei der Auswahl eines Objektes mehr Kartenkontext sichtbar ist. <br /> Als Ausblick für zukünftige Forschung werden Potenziale zur Weiterentwicklung der vorgestellten Interaktionstechniken skizziert, sowie weiterführende Formen von Nutzerstudien diskutiert.