2024
Sven Gedicke. Beyond Zooming: Models and Algorithms for Mobile Maps with Extended Interaction Techniques.. Rheinische Friedrich-Wilhelms-Universität Bonn, 2024. Dissertation.
| |
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. 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, zoomless maps 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. In particular, different variants of zoomless maps 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. 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. Beyond quantitatively evaluating the developed models and algorithms, one key objective of this thesis is to verify the usability and utility of zoomless maps 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 zoomless maps 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 zoomless maps 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. The exploration of ways to validate a broader generalizability of the benefits of zoomless maps as well as possible development potentials are outlined as part of future research. @phdthesis{gedicke2024thesis, | |
Sven Gedicke, Shiyaza Risvi, and Jan-Henrik Haunert. Report on the FAIRagro Workshop on Data Quality for Data Analytics in Agrosystem Science (DQ4DA). Technical Report, University of Bonn, 2024.
| |
@techreport{gedicke2024dq4da, |
2023
Sven Gedicke, Martin Tomko, Stephan Winter, and Jan-Henrik Haunert. Selecting Landmarks for Wayfinding Assistance Based on Advance Visibility. In Proc. 31st ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM SIGSPATIAL'23), pages 1-10. 2023.
| |
@inproceedings{gedicke2023selecting, | |
Sven Gedicke, Lukas Arzoumanidis, and Jan-Henrik Haunert. Automating the External Placement of Symbols for Point Features in Situation Maps for Emergency Response. Cartography and Geographic Information Science, 50(4):385-402, 2023.
| |
@article{gedicke2023automating, | |
Sven Gedicke, Lukas Arzoumanidis, and Jan-Henrik Haunert. 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.
| |
@article{gedicke2023lageskizze, | |
Sven Gedicke, and Jan-Henrik Haunert. An Empirical Study on Interfaces for Presenting Large Sets of Point Features in Mobile Maps. The Cartographic Journal, 60(1):25-42, 2023.
| |
@article{gedicke2023empirical, |
2022
Sven Gedicke, Adalat Jabrayilov, Benjamin Niedermann, Petra Mutzel, and Jan-Henrik Haunert. Point feature label placement for multi-page maps on small-screen devices. In Abstracts of 1st Workshop on Computational Cartography 2022. 2022.
| |
@inproceedings{gedicke2022labelplacement, | |
Peter Rottmann, Makus Wallinger, Annika Bonerath, Sven Gedicke, Martin Nöllenburg, and Jan-Henrik Haunert. MosaicSets: Embedding Set Systems into Grid Graphs. In Abstracts of 1st Workshop on Computational Cartography 2022. 2022.
| |
@inproceedings{rottmann2022mosaicsets_compcart, | |
Peter Rottmann, Makus Wallinger, Annika Bonerath, Sven Gedicke, Martin Nöllenburg, and Jan-Henrik Haunert. Mosaicsets: embedding set systems into grid graphs. IEEE Transactions on Visualization and Computer Graphics, 29(1):875-885, 2022.
| |
Visualizing sets of elements and their relations is an important research area in information visualization. In this paper, we present MosaicSets : a novel approach to create Euler-like diagrams from non-spatial set systems such that each element occupies one cell of a regular hexagonal or square grid. The main challenge is to find an assignment of the elements to the grid cells such that each set constitutes a contiguous region. As use case, we consider the research groups of a university faculty as elements, and the departments and joint research projects as sets. We aim at finding a suitable mapping between the research groups and the grid cells such that the department structure forms a base map layout. Our objectives are to optimize both the compactness of the entirety of all cells and of each set by itself. We show that computing the mapping is NP-hard. However, using integer linear programming we can solve real-world instances optimally within a few seconds. Moreover, we propose a relaxation of the contiguity requirement to visualize otherwise non-embeddable set systems. We present and discuss different rendering styles for the set overlays. Based on a case study with real-world data, our evaluation comprises quantitative measures as well as expert interviews. @article{rottmann2022mosaicsets, | |
Annika Bonerath, Lukas Temerowski, Sven Gedicke, and Jan-Henrik Haunert. Exploring Spatio-Temporal Event Data on a Smart Watch. Abstracts of the ICA, 5:96, sep 2022.
| |
@article{bonerath2022spatiotemporal, |
2021
Sven Gedicke, Johannes Oehrlein, and Jan-Henrik Haunert. Aggregating land-use polygons considering line features as separating map elements. Cartography and Geographic Information Science, 48(2):124-139, 2021.
| |
Map generalization is the process of deriving small-scale target maps from a large-scale source map or database while preserving valuable information. In this paper we focus on topographic data, in particular areas of different land-use classes and line features representing the road network. When reducing the map scale, some areas need to be merged to larger composite regions. This process is known as area aggregation. Given a planar partition of areas, one usually aims to build geometrically compact regions of sufficient size while keeping class changes small. Since line features (e.g. roads) are perceived as separating elements in a map, we suggest integrating them into the process of area aggregation. Our aim is that boundaries of regions coincide with line features in such a way that strokes (i.e. chains of line features with small angles of deflection) are not broken into short sections. Complementing the criteria of compact regions and preserving land-use information, we consider this aim as a third criterion. Regarding all three criteria, we formalize an optimization problem and solve it with a heuristic approach using simulated annealing. Our evaluation is based on experiments with different parameter settings. In particular, we compare results of a baseline method that considers two criteria, namely compactness and class changes, with results of our new method that additionally considers our stroke-based criterion. Our results show that this third criterion can be substantially improved while keeping the quality with respect to the original two criteria on a similar level. @article{GedickeCaGIS2021, | |
Sven Gedicke, Annika Bonerath, Benjamin Niedermann, and Jan-Henrik Haunert. 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, 2021. https://youtu.be/IuMhk8jp54c
| |
Visualizing spatial data on small-screen devices such as smartphones and smartwatches poses new challenges in computational cartography. The current interfaces for map exploration require their users to zoom in and out frequently. Indeed, zooming and panning are tools suitable for choosing the map extent corresponding to an area of interest. They are not as suitable, however, for resolving the graphical clutter caused by a high feature density since zooming in to a large map scale leads to a loss of context. Therefore, in this paper, we present new external labeling methods that allow a user to navigate through dense sets of points of interest while keeping the current map extent fixed. We provide a unified model, in which labels are placed at the boundary of the map and visually associated with the corresponding features via connecting lines, which are called leaders. Since the screen space is limited, labeling all features at the same time is impractical. Therefore, at any time, we label a subset of the features. We offer interaction techniques to change the current selection of features systematically and, thus, give the user access to all features. We distinguish three methods, which allow the user either to slide the labels along the bottom side of the map or to browse the labels based on pages or stacks. We present a generic algorithmic framework that provides us with the possibility of expressing the different variants of interaction techniques as optimization problems in a unified way. We propose both exact algorithms and fast and simple heuristics that solve the optimization problems taking into account different criteria such as the ranking of the labels, the total leader length as well as the distance between leaders. In experiments on real-world data we evaluate these algorithms and discuss the three variants with respect to their strengths and weaknesses proving the flexibility of the presented algorithmic framework. @article{gbnh-zm-21, | |
S. Gedicke, A. Jabrayilov, B. Niedermann, P. Mutzel, and J.-H. Haunert. Point feature label placement for multi-page maps on small-screen devices. Computers & Graphics, 100:66-80, 2021.
| |
Map applications on mobile devices such as smartphones and smartwatches have become ubiquitous. When visualizing spatial data on such small-screen devices, one major challenge is annotating the data with labels (e.g., small icons). The restricted space requires new visualization techniques as established strategies, such as maximizing the number of placed labels, easily lead to the omission of information. We propose an approach that distributes all labels contained in a temporarily fixed map section on multiple pages. Applying interaction techniques for navigating through the pages, a user can access all information both without any overlapping labels and without the need for zooming. We propose a method with two phases; a pre-processing phase and a query phase. We use an optimization approach to pre-compute labelings on the level of a whole city and provide the on-demand querying of individual labelings at a more local level. Our approach provides a consistent label-page assignment, meaning that labels do not appear and disappear when the user pans the map. Further, our model provides quick access to important information and a spatially balanced distribution of labels on pages. In experiments on real-world data we analyze different parameter settings and show that our model yields high-quality labelings. @article{gjnmh-zm-21, |
2019
S. Gedicke, B. Niedermann, and J.-H. Haunert. Multi-page Labeling of Small-screen Maps with a Graph-coloring Approach. In LBS 2019: 15th International Conference on Location Based Services, November 11-13, 2019, Vienna, AT. 2019.
| |
Annotating small-screen maps with additional content such as labels for points of interest is a highly challenging problem that requires new algorithmic solutions. A common labeling approach is to select a maximum-size subset of all labels such that no two labels constitute a graphical conflict and to display only the selected labels in the map. A disadvantage of this approach is that a user often has to zoom in and out repeatedly to access all points of interest in a certain region. Since this can be very cumbersome, we suggest an alternative approach that allows the scale of the map to be kept fixed. Our approach is to distribute all labels on multiple pages through which the user can navigate, for example, by swiping the pages from right to left. We in particular optimize the assignment of the labels to pages such that no page contains two conflicting labels, more important labels appear on the first pages, and sparsely labeled pages are avoided. Algorithmically, we reduce this problem to a weighted and constrained graph coloring problem based on a graph representing conflicts between labels such that an optimal coloring of the graph corresponds to a multi-page labeling. We propose a simple greedy heuristic that is fast enough to be deployed in web-applications. We evaluate the quality of the obtained labelings by comparing them with optimal solutions, which we obtain by means of integer linear programming formulations. In our evaluation on real-world data we particularly show that the proposed heuristic achieves near-optimal solutions with respect to the chosen objective function and that it substantially improves the legibility of the labels in comparison to the simple strategy of assigning the labels to pages solely based on the labels' weights. @inproceedings{gedicke2019a, |