Stop-and-go laser scanning is becoming increasingly prevalent in a variety of applications, e.g., the survey of the built environment. For this, a surveyor needs to select a set of standpoints as well as the route between them. This choice, however, has a high impact on both the economic efficiency of the respective survey as well as the completeness, accuracy, and subsequent registrability of the resulting point cloud. Assuming a set of building footprints as input, this article proposes a one-step optimization method to find the minimal number of selected standpoints based on scanner-related constraints. At the same time, we incorporate the length of the shortest route connecting the standpoints in the objective function. A local search method to speed up the time for solving the corresponding Mixed-Integer Linear Program (MILP) is additionally presented. The results for different scenarios show constantly shorter routes in comparison to existing approaches while still maintaining the minimal number of standpoints. Moreover, in our formulation we aim to minimize the effects of inaccuracies in the software-based registration. Inspired by the ideas of network survivability, we to this end propose a novel definition of connectivity tailored for laser scanning networks. On this basis, we enforce redundancy for the registration network of the survey. To prove the applicability of our formulation, we applied it to a large real-world scenario. This paves the way for the future use of fully automatic autonomous systems to provide a complete and high-quality model of the underlying building scenery.

doi:https://doi.org/10.1016/j.isprsjprs.2025.03.017

@article{knechtel2025scanPlanningNetwRedundancy,
    abstract = {Stop-and-go laser scanning is becoming increasingly prevalent in a variety of applications, e.g., the survey of the built environment. For this, a surveyor needs to select a set of standpoints as well as the route between them. This choice, however, has a high impact on both the economic efficiency of the respective survey as well as the completeness, accuracy, and subsequent registrability of the resulting point cloud. Assuming a set of building footprints as input, this article proposes a one-step optimization method to find the minimal number of selected standpoints based on scanner-related constraints. At the same time, we incorporate the length of the shortest route connecting the standpoints in the objective function. A local search method to speed up the time for solving the corresponding Mixed-Integer Linear Program (MILP) is additionally presented. The results for different scenarios show constantly shorter routes in comparison to existing approaches while still maintaining the minimal number of standpoints. Moreover, in our formulation we aim to minimize the effects of inaccuracies in the software-based registration. Inspired by the ideas of network survivability, we to this end propose a novel definition of connectivity tailored for laser scanning networks. On this basis, we enforce redundancy for the registration network of the survey. To prove the applicability of our formulation, we applied it to a large real-world scenario. This paves the way for the future use of fully automatic autonomous systems to provide a complete and high-quality model of the underlying building scenery.},
    author = {Knechtel, Julius and Dehbi, Youness and Klingbeil, Lasse and Haunert, Jan-Henrik},
    doi = {https://doi.org/10.1016/j.isprsjprs.2025.03.017},
    issn = {0924-2716},
    journal = {ISPRS Journal of Photogrammetry and Remote Sensing},
    pages = {59-74},
    title = {Simultaneous Planning of Standpoints and Routing for Laser Scanning of Buildings with Network Redundancy},
    url = {https://www.sciencedirect.com/science/article/pii/S0924271625001157},
    volume = {224},
    year = {2025}
}

Historical maps represent an invaluable memory which should be preserved. Such kind of maps are, however, mostly scanned and stored as raster graphics which do not contain semantic information in a machine-readable form. To achieve a machine-readable state, an often expensive human intervention is needed in a fully manual or semi-automatic fashion. An automatic interpretation and a feature extraction is then inevitable for a map digitization and vectorization. Automatic approaches showed more and more convincing and promising results on challenging map corpora avoiding human interaction. This paper deals with the semantic segmentation of historical maps based on Graph Convolutional Networks (GCNs) to capture long-range dependencies between image features. This allows for an extension of the receptive field of Convolutional Neural Networks (CNNs) restricted on local dependencies. A Self-Constructing Graph (SCG) module has been applied to automatically induce the structure of the GCN. We performed experiments revealing promising results where our approach achieved an Mean Intersection over Union (mIoU) of 0.68, outperforming a state-of-the-art CNN dedicated to the semantic segmentation of historical maps.

doi:10.1080/15230406.2025.2468304

@article{arzoumanidis2025semSegHistMaps,
    abstract = {Historical maps represent an invaluable memory which should be preserved. Such kind of maps are, however, mostly scanned and stored as raster graphics which do not contain semantic information in a machine-readable form. To achieve a machine-readable state, an often expensive human intervention is needed in a fully manual or semi-automatic fashion. An automatic interpretation and a feature extraction is then inevitable for a map digitization and vectorization. Automatic approaches showed more and more convincing and promising results on challenging map corpora avoiding human interaction. This paper deals with the semantic segmentation of historical maps based on Graph Convolutional Networks (GCNs) to capture long-range dependencies between image features. This allows for an extension of the receptive field of Convolutional Neural Networks (CNNs) restricted on local dependencies. A Self-Constructing Graph (SCG) module has been applied to automatically induce the structure of the GCN. We performed experiments revealing promising results where our approach achieved an Mean Intersection over Union (mIoU) of 0.68, outperforming a state-of-the-art CNN dedicated to the semantic segmentation of historical maps.},
    author = {Lukas Arzoumanidis and Julius Knechtel and Jan-Henrik Haunert and Youness Dehbi},
    doi = {10.1080/15230406.2025.2468304},
    journal = {Cartography and Geographic Information Science},
    number = {0},
    pages = {},
    title = {Semantic segmentation of historical maps using Self-Constructing Graph Convolutional Networks},
    url = {https://www.tandfonline.com/doi/full/10.1080/15230406.2025.2468304},
    volume = {},
    year = {2025}
}

@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}
}