Map Generalization and Set Visualization Through Spatial Unit Allocation

Abstract

Data visualization is an important aspect of making complex data accessible to a wide audience. Capturing key information in visualized data is critical for users to understand the data and make informed decisions. On the one hand, the data may contain geospatial information, which is often visualized using maps. When navigating maps that visualize spatial data, changing the zoom level is a common strategy for controlling the level of detail. Reducing the level of detail of a map is a key challenge in cartography and can be addressed with map generalization. These changes in level of detail while zooming should be monotonous. On the other hand, the visualization of abstract data, such as set systems, is a well-established field of research in information visualization. Set systems contain information about set elements and their relationships, e.g. working groups and their research projects within a faculty. Set visualization have proven to be a powerful tool for presenting large amounts of data to a user in a compact way. Seeing the interactions between sets in a visualization is easier to understand than reading a description of those interactions. However, both types of data, geospatial and abstract, can become overwhelming for the user if every detail is visualized. <br /> In this thesis, we present optimization approaches for creating generalizations for both geospatial data and set systems. In our algorithms, we adapt some approaches from the research field of spatial unit allocation. When generalizing geospatial data, we aggregate small polygons into larger areas, aiming for a set of representative output polygons. We use our approach to compute a set of solutions that contains an optimal solution for each value of the parameter which controls the level of generalization. For set systems, we present the first approach that is able to determine whether a given set system can be completely displayed as an Euler diagram that satisfies certain <em>wellformedness conditions</em>. If a complete visualization is not possible or required, we aim to create a visualization that either shows as much information as possible or improves readability by losing minimal information. Such a resulting set system can be visualized with our novel visualization technique called <em>MosaicSets</em>. The novel technique builds on an underlying grid and creates a mosaic-like visualization of the set system. We optimize each set to form a compact region to improve the readability of the diagram. For all our approaches, we provide theoretical analysis and evaluate the performance of our algorithms on numerous real-world datasets.

Datenvisualisierung ist ein wichtiger Aspekt, um komplexe Daten einem breiten Publikum zugänglich zu machen. Dabei ist die Erfassung von Schlüsselinformationen entscheidend, um die Daten zu verstehen und fundierte Entscheidungen treffen zu können. Einerseits können die Daten raumbezogene Informationen enthalten, die oft als Karten dargestellt werden. Bei der Handhabung dieser Karten ist die Änderung der Zoomstufe eine gängige Vorgehensweise zur Steuerung des Detailgrads. Diese Änderungen sollten monoton sein. Die Verringerung des Detaillierungsgrads ist eine zentrale Herausforderung in der Kartografie und kann durch Generalisierung der Karten gelöst werden. Andererseits ist die Visualisierung abstrakter Daten, wie z.B. von Mengensystemen, ein etabliertes Forschungsgebiet in der Informationsvisualisierung. Mengensysteme enthalten Informationen über Mengenelemente und deren Beziehungen, z.B. Arbeitsgruppen und deren gemeinsame Forschungsprojekte. Die Visualisierung von Mengen hat sich als ein leistungsfähiges Werkzeug herausgestellt, um dem Nutzer große Datenmengen in kompakter Form darzustellen. Visualisierte Beziehungen zwischen Mengen lassen sich leichter verstehen als textuelle Beschreibungen. Allerdings vereint raumbezogene und abstrakte Daten, dass es für den Nutzer überfordernd sein kann, wenn jedes Detail dargestellt wird. <br /> In dieser Arbeit werden Optimierungsansätze für die Erstellung von Generalisierungen für Geodaten und für Mengensysteme vorgestellt. In den Algorithmen werden Ansätze aus dem Forschungsbereich der Zuweisung räumlicher Flächeneinheiten adaptiert. Bei der Generalisierung von Geodaten werden kleine Polygone zu größeren Flächen zusammengefasst. Dieser Algorithmus wird verwendet, um eine Lösungsmenge zu berechnen, welche eine optimale Lösung für jeden Parameterwert, welcher den Grad der Generalisierung bestimmt, enthält. Für Mengensysteme wird der erste Ansatz vorgestellt, welcher bestimmt, ob ein gegebenes Mengensystem unter Berücksichtigung von <em>Wohlgeformtheitsbedingungen</em> vollständig als Euler-Diagramm dargestellt werden kann. Wenn eine vollständige Darstellung nicht möglich oder erforderlich ist, ist es das Ziel, eine Darstellung zu erzeugen, die entweder so viele Informationen wie möglich zeigt oder die Lesbarkeit durch das Entfernen minimaler Informationen verbessert. Ein solches Mengensystem kann mit der neuen eingeführten Visualisierungstechnik <em>MosaicSets</em> visualisiert werden. Diese baut auf einem zugrunde liegenden Raster auf und erzeugt eine mosaikartige Visualisierung des Mengensystems. Jede Menge wird so optimiert, dass sie eine kompakte Region bildet, um die Lesbarkeit des Diagramms zu verbessern. Für alle gezeigten Ansätze werden theoretische Analysen erstellt und die Leistung der Algorithmen anhand zahlreicher realer Datensätze bewertet.