@inproceedings{bonerath2025bubblecharts,
    author = {Bonerath, Annika and Evans, William and Haunert, Jan-Henrik and Kirkpatrick, David and Kobourov, Stephen},
    booktitle = {Proceedings of the 40th European Workshop on Computational Geometry (EuroCG'24)},
    note = {Preprint. Accepted for publiaction.},
    title = {{Disc Placement for Dynamic Bubble Charts}},
    year = {2025}
}

doi:10.48565/bonndoc-515

@phdthesis{bonerath2025thesis,
    author = {Bonerath, Annika },
    doi = {10.48565/bonndoc-515},
    school = {Rheinische Friedrich-Wilhelms-Universität Bonn},
    title = {{G}eometric {A}lgorithms for the {V}isual {E}xploration of {S}patiotemporal {D}ata},
    type = {Dissertation},
    url = {https://hdl.handle.net/20.500.11811/12847},
    year = {2025}
}

User interfaces for inspecting spatio-temporal events often allow their users to filter the events by specifying a time window with a time slider. We consider the case that filtered events are visualized on a map using textual or iconic labels. However, to ensure a clear visualization, not all filtered events are annotated with a label. We present algorithms for setting up a data structure that encodes for every possible time window the set of displayed labels. Our algorithms ensure that the displayed labels never overlap and guarantee the stability of the labeling during certain basic interactions with the time slider. Assuming that the labels have different priorities (weights), we aim to maximize the weight of the displayed labels integrated over all possible time windows. As basic interactions, we consider moving the entire time window, symmetrically scaling it, and dragging one of its endpoints. We consider two stability requirements: (1) during a basic interaction, a label should appear and disappear at most once; (2) if a label is displayed for a time window $Q$, then it is also displayed for all the time windows contained in $Q$ and that contain its timestamp. We prove that finding an optimal solution is NP-hard and propose efficient constant-factor approximation algorithms for unit-square and unit- disk labels, as well as a fast greedy heuristic for arbitrarily shaped labels. In experiments on real-world data, we compare the non-exact algorithms with an exact approach through integer linear programming.

doi:10.1109/TVCG.2025.3527582

@article{bonerath2025twl,
    abstract = { User interfaces for inspecting spatio-temporal events often allow their users to filter the events by specifying a time window with a time slider. We consider the case that filtered events are visualized on a map using textual or iconic labels. However, to ensure a clear visualization, not all filtered events are annotated with a label. We present algorithms for setting up a data structure that encodes for every possible time window the set of displayed labels. Our algorithms ensure that the displayed labels never overlap and guarantee the stability of the labeling during certain basic interactions with the time slider. Assuming that the labels have different priorities (weights), we aim to maximize the weight of the displayed labels integrated over all possible time windows. As basic interactions, we consider moving the entire time window, symmetrically scaling it, and dragging one of its endpoints. We consider two stability requirements: (1) during a basic interaction, a label should appear and disappear at most once; (2) if a label is displayed for a time window $Q$, then it is also displayed for all the time windows contained in $Q$ and that contain its timestamp. We prove that finding an optimal solution is NP-hard and propose efficient constant-factor approximation algorithms for unit-square and unit- disk labels, as well as a fast greedy heuristic for arbitrarily shaped labels. In experiments on real-world data, we compare the non-exact algorithms with an exact approach through integer linear programming. },
    address = {Los Alamitos, CA, USA},
    author = {Bonerath, Annika and Driemel, Anne and Haunert, Jan-Henrik and Haverkort, Herman and Langetepe, Elmar and Niedermann, Benjamin},
    doi = {10.1109/TVCG.2025.3527582},
    issn = {1941-0506},
    journal = { IEEE Transactions on Visualization \& Computer Graphics },
    keywords = {Labeling;Data visualization;Annotations;Tornadoes;Heuristic algorithms;Data structures;Spatial databases;Reproducibility of results;Earthquakes;Approximation algorithms},
    number = {01},
    pages = {1-15},
    publisher = {IEEE Computer Society},
    title = {{ Algorithms for Consistent Dynamic Labeling of Maps With a Time-Slider Interface }},
    url = {https://doi.ieeecomputersociety.org/10.1109/TVCG.2025.3527582},
    volume = {},
    year = {2025}
}

Routing through a dynamic environment is mostly carried out by using maps that integrate information about time-dependent parameters, such as traffic conditions and spatial constraints, which is a challenging and cumbersome task. We address the complex scenario where a user has to plan a route on a network that is dynamic with respect to edges that change their congestion through time. We perform an experimental user study where we compare interactive and non-interactive interfaces, the complexity levels of the map structures (number of nodes and edges) and of the paths (number of nodes that need to be visited), and the effects of familiarity with the map. The results of our study indicate that an interactive interface is more beneficial than a non-interactive interface for more complex paths, while a non-interactive interface is more beneficial than an interactive interface for less complex paths. In detail, while the number of nodes and edges of the network had no effect on the performance, we observed that (not surprisingly) the more complex the path, the longer the processing time and the lower the correctness. We tested the familiarity with a test–retest design, where we organized a second session of tests, labeled T2, after the first session T1. We observed a familiarization effect in T2, that is, the participants’ performance improved for the networks known from T1.

doi:10.2352/J.Percept.Imaging.2025.8.000401

@article{bonerath2025userstudy,
    abstract = {Routing through a dynamic environment is mostly carried out by using maps that integrate information about time-dependent parameters, such as traffic conditions and spatial constraints, which is a challenging and cumbersome task. We address the complex scenario where a user has to plan a route on a network that is dynamic with respect to edges that change their congestion through time. We perform an experimental user study where we compare interactive and non-interactive interfaces, the complexity levels of the map structures (number of nodes and edges) and of the paths (number of nodes that need to be visited), and the effects of familiarity with the map. The results of our study indicate that an interactive interface is more beneficial than a non-interactive interface for more complex paths, while a non-interactive interface is more beneficial than an interactive interface for less complex paths. In detail, while the number of nodes and edges of the network had no effect on the performance, we observed that (not surprisingly) the more complex the path, the longer the processing time and the lower the correctness. We tested the familiarity with a test–retest design, where we organized a second session of tests, labeled T2, after the first session T1. We observed a familiarization effect in T2, that is, the participants’ performance improved for the networks known from T1.},
    author = {Annika Bonerath and Claus-Christian Carbon and Silvia Miksch and Maurizio Patrignani and Alessandra Tappini},
    doi = {10.2352/J.Percept.Imaging.2025.8.000401},
    journal = {Journal of Perceptual Imaging},
    keywords = {spatio-temporal networks, route planning, user study, complexity, navigation},
    number = {0},
    pages = {1--1},
    title = {Time-Dependent Route Planning on Maps: A User Study},
    url = {https://library.imaging.org/jpi/articles/8/0/000401},
    volume = {8},
    year = {2025}
}

An important task of pattern recognition and map generalization is to partition a set of disjoint polygons into groups and to aggregate the polygons within each group to a representative output polygon. We introduce a new method for this task called bicriteria shapes. Following a classical approach, we define the output polygons by merging the input polygons with a set of triangles that we select from a conforming Delaunay triangulation of the input polygons’ exterior. The innovation is that we control the selection of triangles with a bicriteria optimization model that is efficiently solved via graph cuts. In particular, we minimize a weighted sum that combines the total area of the output polygons and their total perimeter. In a basic problem, we ask for a single solution that is optimal for a preset parameter value. In a second problem, we ask for a set containing an optimal solution for every possible value of the parameter. We discuss how this set can be approximated with few solutions and show that it is hierarchically nested. Hence, the output is a hierarchical clustering that corresponds to multiple levels of detail. An evaluation with building footprints as input and a comparison with α-shapes that are based on the same underlying triangulation conclude the article. An advantage of bicriteria shapes compared to α-shapes is that the sequence of solutions for decreasing values of the parameter is monotone with respect to the total perimeter of the output polygons, resulting in a monotonically decreasing visual complexity.

doi:10.1145/3705001

@article{rottmann2025bicriteriashapes,
    abstract = {An important task of pattern recognition and map generalization is to partition a set of disjoint polygons into groups and to aggregate the polygons within each group to a representative output polygon. We introduce a new method for this task called bicriteria shapes. Following a classical approach, we define the output polygons by merging the input polygons with a set of triangles that we select from a conforming Delaunay triangulation of the input polygons’ exterior. The innovation is that we control the selection of triangles with a bicriteria optimization model that is efficiently solved via graph cuts. In particular, we minimize a weighted sum that combines the total area of the output polygons and their total perimeter. In a basic problem, we ask for a single solution that is optimal for a preset parameter value. In a second problem, we ask for a set containing an optimal solution for every possible value of the parameter. We discuss how this set can be approximated with few solutions and show that it is hierarchically nested. Hence, the output is a hierarchical clustering that corresponds to multiple levels of detail. An evaluation with building footprints as input and a comparison with α-shapes that are based on the same underlying triangulation conclude the article. An advantage of bicriteria shapes compared to α-shapes is that the sequence of solutions for decreasing values of the parameter is monotone with respect to the total perimeter of the output polygons, resulting in a monotonically decreasing visual complexity.},
    address = {New York, NY, USA},
    articleno = {3},
    author = {Rottmann, Peter and Driemel, Anne and Haverkort, Herman and R\"{o}glin, Heiko and Haunert, Jan-Henrik},
    doi = {10.1145/3705001},
    issn = {2374-0353},
    issue_date = {March 2025},
    journal = {ACM Transactions on Spatial Algorithms and Systems},
    keywords = {Map generalization, aggregation, graph cuts, bicriteria optimization},
    month = {2},
    number = {1},
    numpages = {23},
    pages = {1--23},
    publisher = {Association for Computing Machinery},
    title = {Bicriteria Shapes: Hierarchical Grouping and Aggregation of Polygons with an Efficient Graph-Cut Approach},
    volume = {11},
    year = {2025}
}

doi:10.1016/j.atech.2025.100786

@article{baltzer2025smart,
    author = {Baltzer, Dorian and Douglas, Shannon and Haunert, Jan-Henrik and Dehbi, Youness and Tiemann, Inga},
    doi = {10.1016/j.atech.2025.100786},
    journal = {Smart Agricultural Technology},
    pages = {100786},
    publisher = {Elsevier},
    title = {Smart Glasses in the Chicken Barn: Enhancing Animal Welfare Through Mixed Reality},
    url = {https://www.sciencedirect.com/science/article/pii/S2772375525000206?via%3Dihub},
    volume = {10},
    year = {2025}
}