This thesis presents a new method for aggregating area objects in topographic databases. Aggregation is an important sub-problem of automatic generalization, which in cartography and geoinformatics means to derive representations of higher abstraction and smaller scale from given datasets. The developed method aims to create results of maximum quality and to ensure standards like minimal dimensions that are given with database specifications. Basically, two quality criteria are considered relevant: (1) Large-scale objects are to be represented by small-scale objects of semantically similar classes - this aim is formalized by defining a semantic distance between classes. (2) Areas in the smaller scale need to have a geometrically simple, compact shape. For the first time, this task is consequently formulated as an optimization problem and solved by applying combinatorial optimization techniques. In a simplified form, the problem can be stated as follows: Given a planar map with areas of different classes and a minimal allowed area size theta for the target scale, combine the areas into contiguous regions and define a new class for each region, such that each region has size at least theta and the area covered by objects whose classes change is minimized. It will be proven that this simplified problem is already NP-hard. Therefore, it is unlikely that an exact polynomial-time algorithm exists for its solution. This motivates an approach to the problem that is based on mixed-integer linear programming and heuristics. The proposed methods allow semantic class distances and different compactness measures to be considered. These criteria are incorporated into the cost function that is minimized. Furthermore, it is possible to define size thresholds for different classes, in order to preserve objects of high priority. Due to the high complexity of the problem, the exact solution cannot be obtained for large problem instances. Nevertheless, for small instances, the approach allows the results of heuristics to be compared with optimal solutions. This enables the performance of heuristic methods to be assessed with respect to the quality of the result. The development of the presented heuristics is motivated by two aims: Firstly, large problem instances, for example, national topographic databases, need to be generalized. Secondly, local updates need to be propagated into a previously derived small-scale map without processing the complete dataset again. In addition to heuristics that eliminate certain variables in the mixed-integer programs, a heuristic is proposed that decomposes a problem instance into smaller, independent instances. With this approach both aims are achieved. Furthermore, a generalization workflow is presented that, in addition to the aggregation method, comprises methods for area collapse and line simplification. In order to prove the applicability of the proposed method in practice, it was applied to a dataset of the official German topographic database ATKIS. A dataset of the ATKIS DLM 50 was processed, which contains similar amounts of detail as the digital topographic map at scale 1:50 000 (DTK 50). The minimal allowed size theta was defined according to existing specifications of the ATKIS DLM 250. A dataset of 22 km times 22 km with 5537 areas (a map sheet of the DTK 50) was aggregated in 82 minutes. Compared to an existing iterative approach (the so-called region-growing), the new method resulted in 20% less class change and 2% less cost for non-compact shapes. The developed method has several advantages, in particular, it offers results of high semantic accuracy. Furthermore, the proposed optimization method is deterministic and allows (hard) constraints to be handled. These are advantages compared to existing optimization methods for map generalization, which are often based on iterative meta-heuristics like simulated annealing. How to adapt the developed approach to other generalization tasks - in particular to building simplification - is discussed as a question for future research.

@phdthesis{haunert2008f,
    abstract = {This thesis presents a new method for aggregating area objects in topographic databases. Aggregation is an important sub-problem of automatic generalization, which in cartography and geoinformatics means to derive representations of higher abstraction and smaller scale from given datasets. The developed method aims to create results of maximum quality and to ensure standards like minimal dimensions that are given with database specifications. Basically, two quality criteria are considered relevant: (1) Large-scale objects are to be represented by small-scale objects of semantically similar classes - this aim is formalized by defining a semantic distance between classes. (2) Areas in the smaller scale need to have a geometrically simple, compact shape. For the first time, this task is consequently formulated as an optimization problem and solved by applying combinatorial optimization techniques. In a simplified form, the problem can be stated as follows: Given a planar map with areas of different classes and a minimal allowed area size theta for the target scale, combine the areas into contiguous regions and define a new class for each region, such that each region has size at least theta and the area covered by objects whose classes change is minimized. It will be proven that this simplified problem is already NP-hard. Therefore, it is unlikely that an exact polynomial-time algorithm exists for its solution. This motivates an approach to the problem that is based on mixed-integer linear programming and heuristics. The proposed methods allow semantic class distances and different compactness measures to be considered. These criteria are incorporated into the cost function that is minimized. Furthermore, it is possible to define size thresholds for different classes, in order to preserve objects of high priority. Due to the high complexity of the problem, the exact solution cannot be obtained for large problem instances. Nevertheless, for small instances, the approach allows the results of heuristics to be compared with optimal solutions. This enables the performance of heuristic methods to be assessed with respect to the quality of the result. The development of the presented heuristics is motivated by two aims: Firstly, large problem instances, for example, national topographic databases, need to be generalized. Secondly, local updates need to be propagated into a previously derived small-scale map without processing the complete dataset again. In addition to heuristics that eliminate certain variables in the mixed-integer programs, a heuristic is proposed that decomposes a problem instance into smaller, independent instances. With this approach both aims are achieved. Furthermore, a generalization workflow is presented that, in addition to the aggregation method, comprises methods for area collapse and line simplification. In order to prove the applicability of the proposed method in practice, it was applied to a dataset of the official German topographic database ATKIS. A dataset of the ATKIS DLM 50 was processed, which contains similar amounts of detail as the digital topographic map at scale 1:50 000 (DTK 50). The minimal allowed size theta was defined according to existing specifications of the ATKIS DLM 250. A dataset of 22 km times 22 km with 5537 areas (a map sheet of the DTK 50) was aggregated in 82 minutes. Compared to an existing iterative approach (the so-called region-growing), the new method resulted in 20% less class change and 2% less cost for non-compact shapes. The developed method has several advantages, in particular, it offers results of high semantic accuracy. Furthermore, the proposed optimization method is deterministic and allows (hard) constraints to be handled. These are advantages compared to existing optimization methods for map generalization, which are often based on iterative meta-heuristics like simulated annealing. How to adapt the developed approach to other generalization tasks - in particular to building simplification - is discussed as a question for future research.},
    author = {Haunert, J.-H.},
    file = {c-626.pdf:http\://129.187.165.2/typo3_dgk/docs/c-626.pdf:PDF},
    isbn = {ISBN 978-3-7696-5038-9},
    number = {626},
    school = {Leibniz Universität Hannover, Germany},
    series = {Veröffentlichungen der Deutschen Geodätischen Kommission, Reihe C},
    timestamp = {2011-11-07T12:01:01.000+0100},
    title = {Aggregation in Map Generalization by Combinatorial Optimization},
    type = {Dissertation},
    year = {2009}
}

	Axel Forsch, Ruben Kemna, Elmar Langetepe, and Jan-Henrik Haunert. Polyline morphing for animated schematic maps. Journal of Geovisualization and Spatial Analysis, 8, 2024. abstract doi bibtex
	Thematic maps allow for the visual analysis of spatial data. When comparing two map states, preserving the mental map of a user facilitates the comparison. One way to achieve this is to use animated transitions between the states. This work presents an algorithm for computing such animations, called morphs, between schematized map objects, a technique particularly pertinent in urban mobility scenarios where schematic maps improve map legibility. In schematic maps, abstraction is used to reduce the visual complexity while still conveying information on a selected phenomenon. Our method ensures that the morph has four favorable properties: (1) it is self-intersection-free, (2) it maintains the schematization of the input features, (3) it is self-contained, and (4) every segment moves at its own constant velocity. We present an efficient algorithm to compute vertex traces and the timing of the morph. We evaluate our approach on isochrones visualizing travel times and on different layouts of schematic transit networks. The results show that the additional constraints we induce on the morphing only have a minor influence on the optimization target while they reduce the complexity of the animation. doi:10.1007/s41651-024-00198-w @article{ForschKemna2024, abstract = {Thematic maps allow for the visual analysis of spatial data. When comparing two map states, preserving the mental map of a user facilitates the comparison. One way to achieve this is to use animated transitions between the states. This work presents an algorithm for computing such animations, called morphs, between schematized map objects, a technique particularly pertinent in urban mobility scenarios where schematic maps improve map legibility. In schematic maps, abstraction is used to reduce the visual complexity while still conveying information on a selected phenomenon. Our method ensures that the morph has four favorable properties: (1) it is self-intersection-free, (2) it maintains the schematization of the input features, (3) it is self-contained, and (4) every segment moves at its own constant velocity. We present an efficient algorithm to compute vertex traces and the timing of the morph. We evaluate our approach on isochrones visualizing travel times and on different layouts of schematic transit networks. The results show that the additional constraints we induce on the morphing only have a minor influence on the optimization target while they reduce the complexity of the animation.}, author = {Forsch, Axel and Kemna, Ruben and Langetepe, Elmar and Haunert, Jan-Henrik}, doi = {10.1007/s41651-024-00198-w}, issue = {37}, journal = {Journal of Geovisualization and Spatial Analysis}, pages = {}, title = {Polyline Morphing for Animated Schematic Maps}, volume = {8}, year = {2024} }
	M. Hartig, S. Seifert, J.-H. Haunert, and S. Hüttel. Improving geographical accuracy of agricultural data: a probabilitstic spatial downscaling approach. In volume 59. Schriften der Gesellschaft für Wirtschafts- und Sozialwissenschaften des Landbaues e.V., pages 325-327. 2024. abstract bibtex
	Analyzing agricultural production requires detailed information about agroclimatic conditions at the farm's locations. The widely used Farm Accountancy Data Network (FADN) misses such information and provides farm locations only at NUTS-2 level. To identify farm locations more precisely, we extend the Bayesian probabilistic spatial downscaling approach of KEMPEN et al. (2011) utilizing only open access data, state-of-the-art regression techniques, and crop modeling. Furthermore, we include new data sources to improve the overall prediction accuracy. Preliminary results indicate that an improved spatial downscaling of FADN farm-level data from NUTS-2 to NUTS-3 is possible using publicly available data sources. Our extension introduces an open-access approach to link FADN farm observations to weather and climate variables. @inproceedings{Hartig2024, abstract = {Analyzing agricultural production requires detailed information about agroclimatic conditions at the farm's locations. The widely used Farm Accountancy Data Network (FADN) misses such information and provides farm locations only at NUTS-2 level. To identify farm locations more precisely, we extend the Bayesian probabilistic spatial downscaling approach of KEMPEN et al. (2011) utilizing only open access data, state-of-the-art regression techniques, and crop modeling. Furthermore, we include new data sources to improve the overall prediction accuracy. Preliminary results indicate that an improved spatial downscaling of FADN farm-level data from NUTS-2 to NUTS-3 is possible using publicly available data sources. Our extension introduces an open-access approach to link FADN farm observations to weather and climate variables.}, author = {Hartig, M. and Seifert, S. and Haunert, J.-H. and Hüttel, S.}, booktitle = {{Schriften der Gesellschaft für Wirtschafts- und Sozialwissenschaften des Landbaues e.V.}}, pages = {325--327}, title = {Improving geographical accuracy of agricultural data: A probabilitstic spatial downscaling approach}, url = {https://www.gewisola.de/files/Tagungsband_finale_Version.pdf}, volume = {59}, year = {2024} }
	Julius Knechtel, Peter Rottmann, Jan-Henrik Haunert, and Youness Dehbi. Semantic floorplan segmentation using self-constructing graph networks. Automation in Construction, 166:105649, 2024. abstract doi bibtex
	This article presents an approach for the automatic semantic segmentation of floorplan images, predicting room boundaries (walls, doors, windows) and semantic labels of room types. A multi-task network was designed to represent and learn inherent dependencies by combining a Convolutional Neural Network to generate suitable features with a Graph Convolutional Network (GCN) to capture long-range dependencies. In particular, a Self-Constructing Graph module is applied to automatically induce an input graph for the GCN. Experiments on different datasets demonstrate the superiority and effectiveness of the multi-task network compared to state-of-the-art methods. The accurate results not only allow for subsequent vectorization of the existing floorplans but also for automatic inference of layout graphs including connectivity and adjacency relations. The latter could serve as basis to automatically sample layout graphs for architectural planning and design, predict missing links for unobserved parts for as-built building models and learn important latent topological and architectonic patterns. doi:10.1016/j.autcon.2024.105649 @article{Knechtel2024FloorplanSCG, abstract = {This article presents an approach for the automatic semantic segmentation of floorplan images, predicting room boundaries (walls, doors, windows) and semantic labels of room types. A multi-task network was designed to represent and learn inherent dependencies by combining a Convolutional Neural Network to generate suitable features with a Graph Convolutional Network (GCN) to capture long-range dependencies. In particular, a Self-Constructing Graph module is applied to automatically induce an input graph for the GCN. Experiments on different datasets demonstrate the superiority and effectiveness of the multi-task network compared to state-of-the-art methods. The accurate results not only allow for subsequent vectorization of the existing floorplans but also for automatic inference of layout graphs including connectivity and adjacency relations. The latter could serve as basis to automatically sample layout graphs for architectural planning and design, predict missing links for unobserved parts for as-built building models and learn important latent topological and architectonic patterns.}, author = {Knechtel, Julius and Rottmann, Peter and Haunert, Jan-Henrik and Dehbi, Youness}, doi = {10.1016/j.autcon.2024.105649}, journal = {Automation in Construction}, pages = {105649}, title = {Semantic Floorplan Segmentation Using Self-Constructing Graph Networks}, url = {https://www.sciencedirect.com/science/article/pii/S0926580524003856}, volume = {166}, year = {2024} }
	Reza Arabsheibani, Jan-Henrik Haunert, Stephan Winter, and Martin Tomko. Strategic allocation of landmarks to reduce uncertainty in indoor navigation. Computers, Environment and Urban Systems, , 2024. Accepted for publication. bibtex
	@article{Arabsheibani2024, author = {Arabsheibani, Reza and Haunert, Jan-Henrik and Winter, Stephan and Tomko, Martin}, journal = {Computers, Environment and Urban Systems}, note = {Accepted for publication.}, title = {Strategic Allocation of Landmarks to Reduce Uncertainty in Indoor Navigation}, year = {2024} }
	Alexander Naumann, Annika Bonerath, and Jan-Henrik Haunert. Many-to-many polygon matching \`a la Jaccard. In Proc. European Symposium on Algorithms (ESA'24), pages 90:1-90:15. 2024. abstract doi bibtex
	Integration of spatial data is a major field of research. An important task of data integration is finding correspondences between entities. Here, we focus on combining building footprint data from cadastre and from volunteered geographic information, in particular OpenStreetMap. Previous research on this topic has led to exact 1:1 matching approaches and heuristic m:n matching approaches, most of which are lacking a mathematical problem definition. We introduce a model for many-to-many polygon matching based on the well-established Jaccard index. This is a natural extension to the existing 1:1 matching approaches. We show that the problem is NP-complete and a naive approach via integer programming fails easily. By analyzing the structure of the problem in detail, we can reduce the number of variables significantly. This approach yields an optimal m:n matching even for large real-world instances with appropriate running time. In particular, for the set of all building footprints of the city of Bonn (119,300 / 97,284 polygons) it yielded an optimal solution in approximately 1 hour. doi:10.4230/LIPIcs.ESA.2024.90 @inproceedings{NaumannEtAl2024, abstract = {Integration of spatial data is a major field of research. An important task of data integration is finding correspondences between entities. Here, we focus on combining building footprint data from cadastre and from volunteered geographic information, in particular OpenStreetMap. Previous research on this topic has led to exact 1:1 matching approaches and heuristic m:n matching approaches, most of which are lacking a mathematical problem definition. We introduce a model for many-to-many polygon matching based on the well-established Jaccard index. This is a natural extension to the existing 1:1 matching approaches. We show that the problem is NP-complete and a naive approach via integer programming fails easily. By analyzing the structure of the problem in detail, we can reduce the number of variables significantly. This approach yields an optimal m:n matching even for large real-world instances with appropriate running time. In particular, for the set of all building footprints of the city of Bonn (119,300 / 97,284 polygons) it yielded an optimal solution in approximately 1 hour.}, author = {Naumann, Alexander and Bonerath, Annika and Haunert, Jan-Henrik}, booktitle = {Proc. European Symposium on Algorithms (ESA'24)}, doi = {10.4230/LIPIcs.ESA.2024.90}, pages = {90:1--90:15}, title = {Many-to-many polygon matching \`{a} la {Jaccard}}, year = {2024} }
	Anna-Maria Bolte, Benjamin Niedermann, Thomas Kistemann, Jan-Henrik Haunert, Youness Dehbi, and Theo Kötter. The green window view index: automated multi-source visibility analysis for a multi-scale assessment of green window views. Landscape Ecology, 39, 2024. doi bibtex
	doi:10.1007/s10980-024-01871-7 @article{BolteEtAl2024, author = {Bolte, Anna-Maria and Niedermann, Benjamin and Kistemann, Thomas and Haunert, Jan-Henrik and Dehbi, Youness and Kötter, Theo}, doi = {10.1007/s10980-024-01871-7}, issue = {3}, journal = {Landscape Ecology}, title = {The green window view index: automated multi-source visibility analysis for a multi-scale assessment of green window views}, volume = {39}, year = {2024} }
	Xinyuan Yan, Peter Rodgers, Peter Rottmann, Daniel Archambault, Jan-Henrik Haunert, and Bei Wang. Eulermerge: simplifying euler diagrams through set merges. In volume 14981 of Lecture Notes in Computer Science. Diagrams 2024: 14th International Conference on the Theory and Application of Diagrams, pages 190-206. Springer, 2024. abstract doi bibtex
	Euler diagrams are an intuitive and popular method to visualize set-based data. In an Euler diagram, each set is represented as a closed curve, and set intersections are shown by curve overlaps. However, Euler diagrams are not visually scalable and automatic layout techniques struggle to display real-world data sets in a comprehensible way. Prior state-of-the-art approaches can embed Euler diagrams by splitting a closed curve into multiple curves so that a set is represented by multiple disconnected enclosed areas. In addition, these methods typically result in multiple curve segments being drawn concurrently. Both of these features significantly impede understanding. In this paper, we present a new and scalable method for embedding Euler diagrams using set merges. Our approach simplifies the underlying data to ensure that each set is represented by a single, connected enclosed area and that the diagram is drawn without curve concurrency, leading to wellformed and understandable Euler diagrams. doi:10.1007/978-3-031-71291-3_16 @inproceedings{YanEtAl2024, abstract = {Euler diagrams are an intuitive and popular method to visualize set-based data. In an Euler diagram, each set is represented as a closed curve, and set intersections are shown by curve overlaps. However, Euler diagrams are not visually scalable and automatic layout techniques struggle to display real-world data sets in a comprehensible way. Prior state-of-the-art approaches can embed Euler diagrams by splitting a closed curve into multiple curves so that a set is represented by multiple disconnected enclosed areas. In addition, these methods typically result in multiple curve segments being drawn concurrently. Both of these features significantly impede understanding. In this paper, we present a new and scalable method for embedding Euler diagrams using set merges. Our approach simplifies the underlying data to ensure that each set is represented by a single, connected enclosed area and that the diagram is drawn without curve concurrency, leading to wellformed and understandable Euler diagrams.}, author = {Yan, Xinyuan and Rodgers, Peter and Rottmann, Peter and Archambault, Daniel and Haunert, Jan-Henrik and Wang, Bei}, booktitle = {Diagrams 2024: 14th International Conference on the Theory and Application of Diagrams}, doi = {10.1007/978-3-031-71291-3_16}, pages = {190--206}, publisher = {Springer}, series = {Lecture Notes in Computer Science}, title = {{EulerMerge: Simplifying Euler Diagrams Through Set Merges}}, volume = {14981}, year = {2024} }
	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. doi bibtex
	doi:10.5281/zenodo.10697161 @techreport{gedicke2024dq4da, author = {Gedicke, Sven and Risvi, Shiyaza and Haunert, Jan-Henrik}, doi = {10.5281/zenodo.10697161}, institution = {University of Bonn}, title = {{R}eport on the {FAIR}agro {W}orkshop on {D}ata {Q}uality for {D}ata {A}nalytics in {A}grosystem {S}cience ({DQ4DA})}, year = {2024} }
	Julius Knechtel, Weilian Li, Yannick Orgeig, Jan-Henrik Haunert, and Youness Dehbi. Immersive Virtual Reality to Verify the As-built State of Electric Line Networks in Buildings. In Thomas H. Kolbe, Andreas Donaubauer, and Christof Beil, editors. Recent Advances in 3D Geoinformation Science (Proceedings of the 18th 3D GeoInfo Conference 2023, Munich), pages 129-143. Springer Nature Switzerland, 2024. abstract doi bibtex
	Immersive virtual reality (IVR) allows viewing abstract concepts and entities in a three dimensional (3D) visuospatial environment. In this paper, we innovatively introduced IVR technology into the verification of the as-built state of electric line networks in buildings. On the one hand, using a reasoning-based estimation of electric networks as a starting point, we demonstrated the usability of IVR technology for verifying installed utilities in buildings. On the other hand, we established the communication between the Reasoner and the practitioner and also simulated the verification action of electric line networks in buildings in the real world. The principal findings of this work pave the way for a subsequent and systematic evaluation of the different reasoning strategies for estimating and generating the as-built state of building utilities. doi:10.1007/978-3-031-43699-4_8 @inproceedings{knechtel2024immersiveVRElectricNetworks, abstract = {Immersive virtual reality (IVR) allows viewing abstract concepts and entities in a three dimensional (3D) visuospatial environment. In this paper, we innovatively introduced IVR technology into the verification of the as-built state of electric line networks in buildings. On the one hand, using a reasoning-based estimation of electric networks as a starting point, we demonstrated the usability of IVR technology for verifying installed utilities in buildings. On the other hand, we established the communication between the Reasoner and the practitioner and also simulated the verification action of electric line networks in buildings in the real world. The principal findings of this work pave the way for a subsequent and systematic evaluation of the different reasoning strategies for estimating and generating the as-built state of building utilities.}, address = {Cham}, author = {Knechtel, Julius and Li, Weilian and Orgeig, Yannick and Haunert, Jan-Henrik and Dehbi, Youness}, booktitle = {Recent Advances in 3D Geoinformation Science (Proceedings of the 18th 3D GeoInfo Conference 2023, Munich)}, doi = {10.1007/978-3-031-43699-4\_8}, editor = {Kolbe, Thomas H. and Donaubauer, Andreas and Beil, Christof}, isbn = {978-3-031-43699-4}, pages = {129--143}, publisher = {Springer Nature Switzerland}, title = {{I}mmersive {V}irtual {R}eality to {V}erify the {A}s-built {S}tate of {E}lectric {L}ine {N}etworks in {B}uildings}, year = {2024} }
	Farzane Mohseni, AmirHossein Ahrari, Jan-Henrik Haunert, and Carsten Montzka. The synergies of smap enhanced and modis products in a random forest regression for estimating 1 km soil moisture over africa using google earth engine. Big Earth Data, 8(1):33-57, 2024. doi bibtex
	doi:10.1080/20964471.2023.2257905 @article{Mohseni2023, author = {Mohseni, Farzane and Ahrari, AmirHossein and Haunert, Jan-Henrik and Montzka, Carsten}, doi = {10.1080/20964471.2023.2257905}, journal = {Big Earth Data}, number = {1}, pages = {33-57}, title = {The synergies of SMAP enhanced and MODIS products in a random forest regression for estimating 1 km soil moisture over Africa using Google Earth Engine}, volume = {8}, year = {2024} }
	Axel Forsch, Stefan Funke, Jan-Henrik Haunert, and Sabine Storandt. Efficient mining of volunteered trajectory datasets. In Dirk Burghardt, Elena Demidova, and Daniel A. Keim, editors. Volunteered Geographic Information: Interpretation, Visualization and Social Context, pages 43-77. Springer Nature Switzerland, 2024. abstract doi bibtex
	With the ubiquity of mobile devices that are capable of tracking positions (be it via GPS or Wi-Fi/mobile network localization), there is a continuous stream of location data being generated every second. These location measurements are typically not considered individually but rather as sequences, each of which reflects the movement of one person or vehicle, which we call trajectory. This chapter presents new algorithmic approaches to process and visualize trajectories both in the network-constrained and the unconstrained case. doi:10.1007/978-3-031-35374-1_3 @incollection{forsch2024volunteered, abstract = {With the ubiquity of mobile devices that are capable of tracking positions (be it via GPS or Wi-Fi/mobile network localization), there is a continuous stream of location data being generated every second. These location measurements are typically not considered individually but rather as sequences, each of which reflects the movement of one person or vehicle, which we call trajectory. This chapter presents new algorithmic approaches to process and visualize trajectories both in the network-constrained and the unconstrained case.}, address = {Cham}, author = {Forsch, Axel and Funke, Stefan and Haunert, Jan-Henrik and Storandt, Sabine}, booktitle = {Volunteered Geographic Information: Interpretation, Visualization and Social Context}, doi = {10.1007/978-3-031-35374-1_3}, editor = {Burghardt, Dirk and Demidova, Elena and Keim, Daniel A.}, isbn = {978-3-031-35374-1}, pages = {43--77}, publisher = {Springer Nature Switzerland}, title = {Efficient Mining of Volunteered Trajectory Datasets}, year = {2024} }
	Dorian Baltzer, Jan-Henrik Haunert, and Axel Forsch. Visualizing the influence of new public transport infrastructure on travel times. KN - Journal of Cartography and Geographic Information, , 2024. abstract doi bibtex
	Due to the global climate change and increasing traffic volumes in cities, a shift from individual to public and multimodal transport is aspired. Travel time is one of the most important aspects for many people when choosing their mode of trans- portation. This leads to the requirement that changes in travel times have to be considered when planning new public trans- port infrastructure. This research paper presents and compares different techniques for visualizing the impact of new lines in existing public transport networks on travel times. The general approach of simulating timetable data and calculating intermodal travel times considering public transport and walking is being applied to two current infrastructure projects in the city of Bonn and the surrounding region. The created maps generally aim to visualize the spread in travel times between existing and extended transportation networks discretized by different spatial units such as rectangles or postal code areas. In comparison to other common methods which typically require two maps for two different scenarios (e.g. in case of isochro- nes), our approach gives the opportunity to combine all relevant information within one map. It is also shown how to apply bivariate choropleth maps for displaying travel times and how to visualize improvements in the accessibility of multiple target points of interest at once. doi:https://doi.org/10.1007/s42489-024-00167-9 @article{Baltzer2024, abstract = {Due to the global climate change and increasing traffic volumes in cities, a shift from individual to public and multimodal transport is aspired. Travel time is one of the most important aspects for many people when choosing their mode of trans- portation. This leads to the requirement that changes in travel times have to be considered when planning new public trans- port infrastructure. This research paper presents and compares different techniques for visualizing the impact of new lines in existing public transport networks on travel times. The general approach of simulating timetable data and calculating intermodal travel times considering public transport and walking is being applied to two current infrastructure projects in the city of Bonn and the surrounding region. The created maps generally aim to visualize the spread in travel times between existing and extended transportation networks discretized by different spatial units such as rectangles or postal code areas. In comparison to other common methods which typically require two maps for two different scenarios (e.g. in case of isochro- nes), our approach gives the opportunity to combine all relevant information within one map. It is also shown how to apply bivariate choropleth maps for displaying travel times and how to visualize improvements in the accessibility of multiple target points of interest at once.}, author = {Baltzer, Dorian and Haunert, Jan-Henrik and Forsch, Axel}, doi = {https://doi.org/10.1007/s42489-024-00167-9}, journal = {KN - Journal of Cartography and Geographic Information}, publisher = {Springer}, title = {Visualizing the Influence of New Public Transport Infrastructure on Travel Times}, url = {https://link.springer.com/article/10.1007/s42489-024-00167-9}, year = {2024} }
	Weilian Li, Lukas Arzoumanidis, Jannik Matijevic, Daham MMohammed Mustafa, Peter Rottmann, Jan-Henrik Haunert, and Youness Dehbi. Safety assessment of cycling routes in urban environments. The International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences, XLVIII-4/W10-2024:125-130, 2024. abstract doi bibtex
	As one of the most well-known forms of active mobility, cycling is an environmentally friendly way to explore a destination, becoming increasingly prevalent worldwide. However, safety is the most severe issue facing cyclists and the essential factor for people who are hesitant to use bikes. In this context, we propose a safety assessment method for cycling routes in urban environments. This work presents how to automatically generate a safe cycling map integrating volunteered geographic information with GIS analysis. We start by extracting the indicators that can possibly contribute to cycling safety from OpenStreetMap. Then, we set up a multivariate linear regression equation to solve the importance of indicators. Afterward, we generate a weighted graph model that represents cycling safety. Taking the City of Bonn, Germany, as an example, we implement our approach for this region. The experiment results show that Bonn is a city for safe cycling, confirming the claim that Bonn is a bike-friendly city. Our findings can also be used to plan the safest route for cycling, thereby enhancing the overall biking experience in Bonn. doi:10.5194/isprs-archives-XLVIII-4-W10-2024-125-2024 @article{li2024safetyassessment, abstract = {As one of the most well-known forms of active mobility, cycling is an environmentally friendly way to explore a destination, becoming increasingly prevalent worldwide. However, safety is the most severe issue facing cyclists and the essential factor for people who are hesitant to use bikes. In this context, we propose a safety assessment method for cycling routes in urban environments. This work presents how to automatically generate a safe cycling map integrating volunteered geographic information with GIS analysis. We start by extracting the indicators that can possibly contribute to cycling safety from OpenStreetMap. Then, we set up a multivariate linear regression equation to solve the importance of indicators. Afterward, we generate a weighted graph model that represents cycling safety. Taking the City of Bonn, Germany, as an example, we implement our approach for this region. The experiment results show that Bonn is a city for safe cycling, confirming the claim that Bonn is a bike-friendly city. Our findings can also be used to plan the safest route for cycling, thereby enhancing the overall biking experience in Bonn.}, author = {Li, Weilian and Arzoumanidis, Lukas and Matijevic, Jannik and Mustafa, Daham MMohammed and Rottmann, Peter and Haunert, Jan-Henrik and Dehbi, Youness}, doi = {10.5194/isprs-archives-XLVIII-4-W10-2024-125-2024}, journal = {The International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences}, pages = {125--130}, title = {Safety Assessment of Cycling Routes in Urban Environments}, url = {https://isprs-archives.copernicus.org/articles/XLVIII-4-W10-2024/125/2024/}, volume = {XLVIII-4/W10-2024}, year = {2024} }
	Peter Rottmann, Peter Rodgers, Xinyuan Yan, Daniel Archambault, Bei Wang, and Jan-Henrik Haunert. Generating euler diagrams through combinatorial optimization. Computer Graphics Forum, 43(3), 2024. abstract doi bibtex
	Can a given set system be drawn as an Euler diagram? We present the first method that correctly decides this question for arbitrary set systems if the Euler diagram is required to represent each set with a single connected region. If the answer is yes, our method constructs an Euler diagram. If the answer is no, our method yields an Euler diagram for a simplified version of the set system, where a minimum number of set elements have been removed. Further, we integrate known wellformedness criteria for Euler diagrams as additional optimization objectives into our method. Our focus lies on the computation of a planar graph that is embedded in the plane to serve as the dual graph of the Euler diagram. Since even a basic version of this problem is known to be NP-hard, we choose an approach based on integer linear programming (ILP), which allows us to compute optimal solutions with existing mathematical solvers. For this, we draw upon previous research on computing planar supports of hypergraphs and adapt existing ILP building blocks for contiguity-constrained spatial unit allocation and the maximum planar subgraph problem. To generate Euler diagrams for large set systems, for which the proposed simplification through element removal becomes indispensable, we also present an efficient heuristic. We report on experiments with data from MovieDB and Twitter. Over all examples, including 850 non-trivial instances, our exact optimization method failed only for one set system to find a solution without removing a set element. However, with the removal of only a few set elements, the Euler diagrams can be substantially improved with respect to our wellformedness criteria. doi:10.1111/cgf.15089 @article{rottmann2024generating, abstract = {Can a given set system be drawn as an Euler diagram? We present the first method that correctly decides this question for arbitrary set systems if the Euler diagram is required to represent each set with a single connected region. If the answer is yes, our method constructs an Euler diagram. If the answer is no, our method yields an Euler diagram for a simplified version of the set system, where a minimum number of set elements have been removed. Further, we integrate known wellformedness criteria for Euler diagrams as additional optimization objectives into our method. Our focus lies on the computation of a planar graph that is embedded in the plane to serve as the dual graph of the Euler diagram. Since even a basic version of this problem is known to be NP-hard, we choose an approach based on integer linear programming (ILP), which allows us to compute optimal solutions with existing mathematical solvers. For this, we draw upon previous research on computing planar supports of hypergraphs and adapt existing ILP building blocks for contiguity-constrained spatial unit allocation and the maximum planar subgraph problem. To generate Euler diagrams for large set systems, for which the proposed simplification through element removal becomes indispensable, we also present an efficient heuristic. We report on experiments with data from MovieDB and Twitter. Over all examples, including 850 non-trivial instances, our exact optimization method failed only for one set system to find a solution without removing a set element. However, with the removal of only a few set elements, the Euler diagrams can be substantially improved with respect to our wellformedness criteria.}, author = {Rottmann, Peter and Rodgers, Peter and Yan, Xinyuan and Archambault, Daniel and Wang, Bei and Haunert, Jan-Henrik}, doi = {10.1111/cgf.15089}, eprint = {https://onlinelibrary.wiley.com/doi/pdf/10.1111/cgf.15089}, journal = {Computer Graphics Forum}, keywords = {CCS Concepts, • Human-centered computing → Information visualization, • Theory of computation → Integer programming, • Mathematics of computing → Hypergraphs}, number = {3}, title = {Generating Euler Diagrams Through Combinatorial Optimization}, url = {https://onlinelibrary.wiley.com/doi/abs/10.1111/cgf.15089}, volume = {43}, year = {2024} }

	Axel Forsch, and Jan-Henrik Haunert. Metrochrones: schematic isochrones for schematic metro maps. The Cartographic Journal, 60:383-401, 2023. doi bibtex
	doi:10.1080/00087041.2023.2284436 @article{ForschHaunert2024, author = {Axel Forsch and Jan-Henrik Haunert}, doi = {10.1080/00087041.2023.2284436}, issue = {4}, journal = {The Cartographic Journal}, pages = {383--401}, title = {Metrochrones: Schematic Isochrones for Schematic Metro Maps}, volume = {60}, year = {2023} }
	Anna Arutyunova, Anne Driemel, Jan-Henrik Haunert, Herman Haverkort, Jürgen Kusche, Elmar Langetepe, Philip Mayer, Petra Mutzel, and Heiko Röglin. Minimum-error triangulations for sea surface reconstruction. Journal of Computational Geometry, 14(2):108-171, 2023. abstract doi bibtex
	We apply state-of-the-art computational geometry methods to the problem of reconstructing a time-varying sea surface from tide gauge records. Our work builds on a recent article by Nitzke et al. (Computers Geosciences, 157:104920, 2021) who have suggested to learn a triangulation $D$ of a given set of tide gauge stations. The objective is to minimize the misfit of the piecewise linear surface induced by $D$ to a reference surface that has been acquired with satellite altimetry. The authors restricted their search to $k$-order Delaunay ($k$-OD) triangulations and used an integer linear program in order to solve the resulting optimization problem. In geometric terms, the input to our problem consists of two sets of points in $ℝ^2$ with elevations: a set $S$ that is to be triangulated, and a set $R$ of reference points. Intuitively, we define the error of a triangulation as the average vertical distance of a point in $R$ to the triangulated surface that is obtained by interpolating elevations of $S$ linearly in each triangle. Our goal is to find the triangulation of $S$ that has minimum error with respect to $R$. In our work, we prove that the minimum-error triangulation problem is NP-hard and cannot be approximated within any multiplicative factor in polynomial time unless $P = NP$. At the same time we show that the problem instances that occur in our application (considering sea level data from several hundreds of tide gauge stations worldwide) can be solved relatively fast using dynamic programming when restricted to $k$-OD triangulations for $k \le 7$. The fast runtime is a result of a set of fixed edges called the $k$-OD fixed-edge graph. Instances for which the number of connected components of the $k$-OD fixed-edge graph is small can be solved within few seconds. doi:10.20382/jocg.v14i2a7 @article{Arutyunova2023, abstract = {We apply state-of-the-art computational geometry methods to the problem of reconstructing a time-varying sea surface from tide gauge records. Our work builds on a recent article by Nitzke et al. (Computers Geosciences, 157:104920, 2021) who have suggested to learn a triangulation $D$ of a given set of tide gauge stations. The objective is to minimize the misfit of the piecewise linear surface induced by $D$ to a reference surface that has been acquired with satellite altimetry. The authors restricted their search to $k$-order Delaunay ($k$-OD) triangulations and used an integer linear program in order to solve the resulting optimization problem. In geometric terms, the input to our problem consists of two sets of points in $\mathbb{R}^2$ with elevations: a set $S$ that is to be triangulated, and a set $R$ of reference points. Intuitively, we define the error of a triangulation as the average vertical distance of a point in $R$ to the triangulated surface that is obtained by interpolating elevations of $S$ linearly in each triangle. Our goal is to find the triangulation of $S$ that has minimum error with respect to $R$. In our work, we prove that the minimum-error triangulation problem is NP-hard and cannot be approximated within any multiplicative factor in polynomial time unless $P = NP$. At the same time we show that the problem instances that occur in our application (considering sea level data from several hundreds of tide gauge stations worldwide) can be solved relatively fast using dynamic programming when restricted to $k$-OD triangulations for $k \le 7$. The fast runtime is a result of a set of fixed edges called the $k$-OD fixed-edge graph. Instances for which the number of connected components of the $k$-OD fixed-edge graph is small can be solved within few seconds.}, author = {Arutyunova, Anna and Driemel, Anne and Haunert, Jan-Henrik and Haverkort, Herman and Kusche, J\"{u}rgen and Langetepe, Elmar and Mayer, Philip and Mutzel, Petra and R\"{o}glin, Heiko}, doi = {10.20382/jocg.v14i2a7}, journal = {Journal of Computational Geometry}, number = {2}, pages = {108--171}, title = {Minimum-error triangulations for sea surface reconstruction}, volume = {14}, year = {2023} }
	Sophie Duong, Peter Rottmann, Jan-Henrik Haunert, and Petra Mutzel. Clustering building footprint polygons based on graph similarity measures. In UrbanAI '23. Proceedings of the 1st ACM SIGSPATIAL International Workshop on Advances in Urban-AI, pages 22-31. Association for Computing Machinery, 2023. abstract doi bibtex
	Footprints of buildings can provide cues about architectural styles and functional types. Learning such latent thematic information from geometry is relevant for various applications, such as urban planning and map generalization. A common task in this context is to cluster a set of building footprints based on their shape characteristics. In this paper, we present a novel method for this task which is based on concepts of graph similarity. We use a graph similarity measure that combines ideas from the Weisfeiler-Lehman-method and optimal transport theory. For the final clustering, we use spectral clustering. To obtain a meaningful graph representation, we propose two algorithms that transform the medial axis of a building footprint into a skeleton graph. We tested our algorithm on a data set from Boston and performed a small user study, where we also compared the results to an existing feature-based clustering method. The study gives a first hint that the results of our algorithm are in line with human similarity perception. Future work is needed to improve the stability of the proposed similarity measure and to confirm our findings with more extensive experiments. doi:10.1145/3615900.3628790 @inproceedings{duong2023clusteringfootprint, abstract = {Footprints of buildings can provide cues about architectural styles and functional types. Learning such latent thematic information from geometry is relevant for various applications, such as urban planning and map generalization. A common task in this context is to cluster a set of building footprints based on their shape characteristics. In this paper, we present a novel method for this task which is based on concepts of graph similarity. We use a graph similarity measure that combines ideas from the Weisfeiler-Lehman-method and optimal transport theory. For the final clustering, we use spectral clustering. To obtain a meaningful graph representation, we propose two algorithms that transform the medial axis of a building footprint into a skeleton graph. We tested our algorithm on a data set from Boston and performed a small user study, where we also compared the results to an existing feature-based clustering method. The study gives a first hint that the results of our algorithm are in line with human similarity perception. Future work is needed to improve the stability of the proposed similarity measure and to confirm our findings with more extensive experiments.}, address = {New York, NY, USA}, author = {Duong, Sophie and Rottmann, Peter and Haunert, Jan-Henrik and Mutzel, Petra}, booktitle = {Proceedings of the 1st ACM SIGSPATIAL International Workshop on Advances in Urban-AI}, doi = {10.1145/3615900.3628790}, isbn = {9798400703621}, keywords = {graph kernels, medial axis, spectral clustering, building footprints, graph similarity}, numpages = {10}, pages = {22--31}, publisher = {Association for Computing Machinery}, series = {UrbanAI '23}, title = {Clustering Building Footprint Polygons Based on Graph Similarity Measures}, url = {https://doi.org/10.1145/3615900.3628790}, year = {2023} }
	Julius Knechtel, Jan Behmann, Jan-Henrik Haunert, and Youness Dehbi. Suitability assessment of different sensors to detect hidden installations for as-built bim. ISPRS Annals of the Photogrammetry, Remote Sensing and Spatial Information Sciences, X-1/W1-2023:263-270, 2023. abstract doi bibtex
	Knowledge on the utilities hidden in the wall, e.g., electric lines or water pipes, is indispensable for work safety and valuable for planning. Since most of the existing building stock originates from the pre-digital era, no models as understood for Building Information Modeling (BIM) exist. To generate these models often labor-intensive procedures are necessary; however, recent research has dealt with the efficient generation and verification of a building’s electric network. In this context, a reliable measurement method is a necessity. In this paper we test different measurement techniques, such as point-wise measurements with hand-held devices or area-based techniques utilizing thermal imaging. For this purpose, we designed and built a simulation environment that allows various parameters to be manipulated under controlled conditions. In this scenario the low-cost handheld devices show promising results, with a precision between 92% and 100% and a recall between 89% and 100%. The expensive thermal imaging camera is also able to detect electric lines and pipes if there is enough power on the line or if the temperature of the water in the pipe and the environment’s temperature are sufficiently different. Nevertheless, while point-wise measurements can directly yield results, the thermal camera requires post-processing in specific analysis software. The results reinforce the idea of using reasoning methods in both the do-it-yourself and commercial sector, to rapidly gather information about hidden installations in a building without prior technical knowledge. This paves the way for, e.g., exploring the possibilities of an implementation and presentation in augmented reality (AR). doi:10.5194/isprs-annals-X-1-W1-2023-263-2023 @article{knechtel2023sensorSuitability, abstract = {Knowledge on the utilities hidden in the wall, e.g., electric lines or water pipes, is indispensable for work safety and valuable for planning. Since most of the existing building stock originates from the pre-digital era, no models as understood for Building Information Modeling (BIM) exist. To generate these models often labor-intensive procedures are necessary; however, recent research has dealt with the efficient generation and verification of a building’s electric network. In this context, a reliable measurement method is a necessity. In this paper we test different measurement techniques, such as point-wise measurements with hand-held devices or area-based techniques utilizing thermal imaging. For this purpose, we designed and built a simulation environment that allows various parameters to be manipulated under controlled conditions. In this scenario the low-cost handheld devices show promising results, with a precision between 92\% and 100\% and a recall between 89\% and 100\%. The expensive thermal imaging camera is also able to detect electric lines and pipes if there is enough power on the line or if the temperature of the water in the pipe and the environment’s temperature are sufficiently different. Nevertheless, while point-wise measurements can directly yield results, the thermal camera requires post-processing in specific analysis software. The results reinforce the idea of using reasoning methods in both the do-it-yourself and commercial sector, to rapidly gather information about hidden installations in a building without prior technical knowledge. This paves the way for, e.g., exploring the possibilities of an implementation and presentation in augmented reality (AR).}, author = {Knechtel, Julius and Behmann, Jan and Haunert, Jan-Henrik and Dehbi, Youness}, doi = {10.5194/isprs-annals-X-1-W1-2023-263-2023}, journal = {ISPRS Annals of the Photogrammetry, Remote Sensing and Spatial Information Sciences}, pages = {263--270}, title = {{S}uitability {A}ssessment of {D}ifferent {S}ensors to {D}etect {H}idden {I}nstallations for {A}s-built {BIM}}, url = {https://isprs-annals.copernicus.org/articles/X-1-W1-2023/263/2023/}, volume = {X-1/W1-2023}, year = {2023} }
	Annika Bonerath, Yannick Orgeig, Jan-Henrik Haunert, and Youness Dehbi. Integrating optimization-based spatial unit allocation into a multi-agent model for the simulation of urban growth. In Proceedings of the 6th ACM SIGSPATIAL International Workshop on GeoSpatial Simulation, pages 19-22. 2023. doi bibtex
	doi:10.1145/3615891.3628012 @inproceedings{inproceedings, address = {Hamburg, Germany}, author = {Bonerath, Annika and Orgeig, Yannick and Haunert, Jan-Henrik and Dehbi, Youness}, booktitle = {Proceedings of the 6th ACM SIGSPATIAL International Workshop on GeoSpatial Simulation}, doi = {10.1145/3615891.3628012}, month = {11}, pages = {19-22}, title = {Integrating Optimization-Based Spatial Unit Allocation into a Multi-Agent Model for the Simulation of Urban Growth}, year = {2023} }
	Lukas Arzoumanidis, Axel Forsch, Jan-Henrik, and Youness Dehbi. Catchment cell visualization for multi-modal public transportation networks. In Proc. 1st ACM SIGSPATIAL Workshop on Sustainable Mobility. 2023. doi bibtex
	doi:10.1145/3615899.3627931 @inproceedings{arzoumanidis2023catchment, address = {Hamburg, Germany}, author = {Lukas Arzoumanidis and Axel Forsch and Jan-Henrik and Youness Dehbi}, booktitle = {Proc. 1st ACM SIGSPATIAL Workshop on Sustainable Mobility}, doi = {10.1145/3615899.3627931}, title = {Catchment cell visualization for multi-modal public transportation networks}, year = {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. doi bibtex
	doi:10.1145/3589132.3625605 @inproceedings{gedicke2023selecting, author = {Gedicke, Sven and Tomko, Martin and Winter, Stephan and Haunert, Jan-Henrik}, booktitle = {Proc. 31st ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM SIGSPATIAL'23)}, doi = {10.1145/3589132.3625605}, pages = {1--10}, title = {{S}electing {L}andmarks for {W}ayfinding {A}ssistance {B}ased on {A}dvance {V}isibility}, year = {2023} }
	A. Bonerath, Y. Dong, and J.-H. Haunert. An efficient data structure providing maps of the frequency of public transit service within user-specified time windows. Advances in Cartography and GIScience of the ICA, 4:1, 2023. Special issue of 31st International Cartographic Conference (ICC'23) doi bibtex
	doi:10.5194/ica-adv-4-1-2023 @article{bonerath2023thetastarstructure, author = {Bonerath, A. and Dong, Y. and Haunert, J.-H.}, doi = {10.5194/ica-adv-4-1-2023}, journal = {Advances in Cartography and GIScience of the ICA}, note = {Special issue of 31st International Cartographic Conference (ICC'23)}, pages = {1}, title = {An Efficient Data Structure Providing Maps of the Frequency of Public Transit Service Within User-Specified Time Windows}, url = {https://ica-adv.copernicus.org/articles/4/1/2023/}, volume = {4}, year = {2023} }
	Weilian Li, Jan-Henrik Haunert, Julius Knechtel, Jun Zhu, Qing Zhu, and Youness Dehbi. Social Media Insights on Public Perception and Sentiment During and After Disasters: The European Floods in 2021 as a Case Study. Transactions in GIS, 27(6):1766-1793, 2023. abstract doi bibtex
	Abstract Detecting and collecting public opinion via social media can provide near real-time information to decision-makers, which plays a vital role in urban disaster management and sustainable development. However, there has been little work focusing on identifying the perception and the sentiment polarity expressed by users during and after disasters, particularly regional flood events. In this article, we comprehensively analyze tweets data related to the “European floods in 2021” over time, topic, and sentiment, forming a complete workflow from data processing, topic modeling, sentiment analysis, and topic and sentiment prediction. The aim is to address the following research questions: (1) What are the public perception and main concerns during and after floods? (2) How does the public sentiment change during and after floods? Results indicate that there is a significant correlation between a flood's trend and the heat of corresponding tweets. The three topics that receive the most public concern are: (1) climate change and global warming; (2) praying for the victims: and (3) disaster situations and information. Negative sentiments are predominant during the floods and will continue for some time. We tested five different classifiers, of which TextCNN-attention turned out to deliver the best predictions in topic and sentiment prediction, and performed well for sparse flood tweets, it can be used to predict the topic and sentiment polarity of a single tweet in real-time during the flood events. Our findings can help disaster agencies to better understand the dynamics of social networks and develop stronger situational awareness towards a disaster, which can contribute to scientifically justified decision-making in urban risk management and also meet the challenges associated with the global sustainable development goal 11 (SDGs) on Sustainable Cities and Communities. doi:https://doi.org/10.1111/tgis.13097 @article{li2023socialMediaDisaster, abstract = {Abstract Detecting and collecting public opinion via social media can provide near real-time information to decision-makers, which plays a vital role in urban disaster management and sustainable development. However, there has been little work focusing on identifying the perception and the sentiment polarity expressed by users during and after disasters, particularly regional flood events. In this article, we comprehensively analyze tweets data related to the “European floods in 2021” over time, topic, and sentiment, forming a complete workflow from data processing, topic modeling, sentiment analysis, and topic and sentiment prediction. The aim is to address the following research questions: (1) What are the public perception and main concerns during and after floods? (2) How does the public sentiment change during and after floods? Results indicate that there is a significant correlation between a flood's trend and the heat of corresponding tweets. The three topics that receive the most public concern are: (1) climate change and global warming; (2) praying for the victims: and (3) disaster situations and information. Negative sentiments are predominant during the floods and will continue for some time. We tested five different classifiers, of which TextCNN-attention turned out to deliver the best predictions in topic and sentiment prediction, and performed well for sparse flood tweets, it can be used to predict the topic and sentiment polarity of a single tweet in real-time during the flood events. Our findings can help disaster agencies to better understand the dynamics of social networks and develop stronger situational awareness towards a disaster, which can contribute to scientifically justified decision-making in urban risk management and also meet the challenges associated with the global sustainable development goal 11 (SDGs) on Sustainable Cities and Communities.}, author = {Li, Weilian and Haunert, Jan-Henrik and Knechtel, Julius and Zhu, Jun and Zhu, Qing and Dehbi, Youness}, doi = {https://doi.org/10.1111/tgis.13097}, journal = {Transactions in GIS}, number = {6}, pages = {1766-1793}, title = {Social {M}edia {I}nsights on {P}ublic {P}erception and {S}entiment {D}uring and {A}fter {D}isasters: {T}he {E}uropean {F}loods in 2021 as a {C}ase {S}tudy}, volume = {27}, year = {2023} }
	Lukas Arzoumanidis, Julius Knechtel, Jan-Henrik Haunert, and Youness Dehbi. Self-Constructing Graph Convolutional Networks for Semantic Segmentation of Historical Maps. Abstracts of the ICA, 6:11, 2023. doi bibtex
	doi:10.5194/ica-abs-6-11-2023 @article{arzoumanidis2023SCGHistMaps, author = {Arzoumanidis, Lukas and Knechtel, Julius and Haunert, Jan-Henrik and Dehbi, Youness}, doi = {10.5194/ica-abs-6-11-2023}, journal = {Abstracts of the ICA}, pages = {11}, title = {{S}elf-{C}onstructing {G}raph {C}onvolutional {N}etworks for {S}emantic {S}egmentation of {H}istorical {M}aps}, volume = {6}, year = {2023} }
	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. doi bibtex
	doi:10.1080/15230406.2023.2213446 @article{gedicke2023automating, author = {Gedicke, Sven and Arzoumanidis, Lukas and Haunert, Jan-Henrik}, doi = {10.1080/15230406.2023.2213446}, journal = {Cartography and Geographic Information Science}, number = {4}, pages = {385--402}, title = {{A}utomating the {E}xternal {P}lacement of {S}ymbols for {P}oint {F}eatures in {S}ituation {M}aps for {E}mergency {R}esponse}, volume = {50}, year = {2023} }
	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. bibtex
	@article{gedicke2023lageskizze, author = {Gedicke, Sven and Arzoumanidis, Lukas and Haunert, Jan-Henrik}, journal = {Zeitschrift für Forschung und Technik im Brandschutz vfdb}, number = {2}, pages = {59--65}, title = {{E}in {A}lgorithmus zur automatischen {P}latzierung taktischer {Z}eichen in der digitalen {L}ageskizze}, volume = {72}, year = {2023} }
	Axel Forsch, Johannes Oehrlein, Benjamin Niedermann, and Jan-Henrik Haunert. Inferring routing preferences from user-generated trajectories using a compression criterion. Journal of Spatial Information Science, 26(5):99-124, 2023. abstract doi bibtex
	The optimal path between two vertices in a graph depends on the optimization objective, which is often defined as a weighted sum of multiple criteria. When integrating two criteria, their relative importance is expressed with a balance factor α. We present a new approach for inferring α from trajectories. The core of our approach is a compression algorithm that requires a graph G representing a transportation network, two edge costs modeling routing criteria, and a path P in G representing the trajectory. It yields a minimum subsequence S of the sequence of vertices of P and a balance factor α, such that the path P can be fully reconstructed from S, G, its edge costs, and α. By minimizing the size of S over α, we learn the balance factor that corresponds best to the user's routing preferences. In an evaluation with crowd-sourced cycling trajectories, we weigh the usage of official signposted cycle routes against other routes. More than 50% of the trajectories can be segmented into five optimal sub-paths or less. Almost 40% of the trajectories indicate that the cyclist is willing to take a detour of 50% over the geodesic shortest path to use an official cycle path. doi:10.5311/JOSIS.2023.26.256 @article{forsch2023inferring, abstract = {The optimal path between two vertices in a graph depends on the optimization objective, which is often defined as a weighted sum of multiple criteria. When integrating two criteria, their relative importance is expressed with a balance factor α. We present a new approach for inferring α from trajectories. The core of our approach is a compression algorithm that requires a graph G representing a transportation network, two edge costs modeling routing criteria, and a path P in G representing the trajectory. It yields a minimum subsequence S of the sequence of vertices of P and a balance factor α, such that the path P can be fully reconstructed from S, G, its edge costs, and α. By minimizing the size of S over α, we learn the balance factor that corresponds best to the user's routing preferences. In an evaluation with crowd-sourced cycling trajectories, we weigh the usage of official signposted cycle routes against other routes. More than 50% of the trajectories can be segmented into five optimal sub-paths or less. Almost 40% of the trajectories indicate that the cyclist is willing to take a detour of 50% over the geodesic shortest path to use an official cycle path.}, author = {Axel Forsch and Johannes Oehrlein and Benjamin Niedermann and Jan-Henrik Haunert}, doi = {10.5311/JOSIS.2023.26.256}, journal = {Journal of Spatial Information Science}, number = {5}, pages = {99--124}, title = {Inferring routing preferences from user-generated trajectories using a compression criterion}, volume = {26}, year = {2023} }
	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. doi bibtex
	doi:10.1080/00087041.2023.2182354 @article{gedicke2023empirical, author = {Gedicke, Sven and Haunert, Jan-Henrik}, doi = {10.1080/00087041.2023.2182354}, journal = {The Cartographic Journal}, number = {1}, pages = {25-42}, title = {{A}n {E}mpirical {S}tudy on {I}nterfaces for {P}resenting {L}arge {S}ets of {P}oint {F}eatures in {M}obile {M}aps}, volume = {60}, year = {2023} }
	Xenia Specka, Daniel Martini, Claus Weiland, Daniel Arend, Senthold Asseng, Franziska Boehm, Til Feike, Juliane Fluck, David Gackstetter, Aida Gonzales-Mellado, Thomas Hartmann, Jan-Henrik Haunert, Florian Hoedt, Carsten Hoffmann, Patrick König, Matthias Lange, Stephan Lesch, Birte Lindstädt, Gunnar Lischeid, Markus Möller, Uwe Rascher, Jochen Christoph Reif, Markus Schmalzl, Matthias Senft, Ulrike Stahl, Nikolai Svoboda, Björn Usadel, Heidi Webber, and Frank Ewert. FAIRagro: Ein Konsortium in der Nationalen Forschungsdateninfrastruktur (NFDI) für Forschungsdaten in der Agrosystemforschung. Informatik Spektrum, 0(0):0, 2023. doi bibtex
	doi:10.1007/s00287-022-01520-w @article{SpeckaEtAl2023, author = {Specka, Xenia and Martini, Daniel and Weiland, Claus and Arend, Daniel and Asseng, Senthold and Boehm, Franziska and Feike, Til and Fluck, Juliane and Gackstetter, David and Gonzales-Mellado, Aida and Hartmann, Thomas and Haunert, Jan-Henrik and Hoedt, Florian and Hoffmann, Carsten and K\"{o}nig, Patrick and Lange, Matthias and Lesch, Stephan and Lindst\"{a}dt, Birte and Lischeid, Gunnar and M\"{o}ller, Markus and Rascher, Uwe and Reif, Jochen Christoph and Schmalzl, Markus and Senft, Matthias and Stahl, Ulrike and Svoboda, Nikolai and Usadel, Bj\"{o}rn and Webber, Heidi and Ewert, Frank}, doi = {10.1007/s00287-022-01520-w}, journal = {Informatik Spektrum}, number = {0}, pages = {0}, title = {{FAIRagro}: {E}in {K}onsortium in der {N}ationalen {F}orschungsdateninfrastruktur ({NFDI}) für {F}orschungsdaten in der {A}grosystemforschung}, volume = {0}, year = {2023} }
	Annika Bonerath, Jan-Henrik Haunert, Joseph S.B. Mitchell, and Benjamin Niedermann. Shortcut hulls: vertex-restricted outer simplifications of polygons. Computational Geometry Theory and Applications, :101983, 2023. abstract doi bibtex
	Let P be a polygon and C a set of shortcuts, where each shortcut is a directed straight-line segment connecting two vertices of P. A shortcut hull of P is another polygon that encloses P and whose oriented boundary is composed of elements from C. We require P and the output shortcut hull to be weakly simple polygons, which we define as a generalization of simple polygons. Shortcut hulls find their application in cartography, where a common task is to compute simplified representations of area features. We aim at a shortcut hull that has a small area and a small perimeter. Our optimization objective is to minimize a convex combination of these two criteria. If no holes in the shortcut hull are allowed, the problem admits a straight-forward solution via computation of shortest paths. For the more challenging case in which the shortcut hull may contain holes, we present a polynomial-time algorithm that is based on computing a constrained, weighted triangulation of the input polygon's exterior. We use this problem as a starting point for investigating further variants, e.g., restricting the number of edges or bends. We demonstrate that shortcut hulls can be used for the schematization of polygons. doi:https://doi.org/10.1016/j.comgeo.2023.101983 @article{BONERATH2023101983, abstract = {Let P be a polygon and C a set of shortcuts, where each shortcut is a directed straight-line segment connecting two vertices of P. A shortcut hull of P is another polygon that encloses P and whose oriented boundary is composed of elements from C. We require P and the output shortcut hull to be weakly simple polygons, which we define as a generalization of simple polygons. Shortcut hulls find their application in cartography, where a common task is to compute simplified representations of area features. We aim at a shortcut hull that has a small area and a small perimeter. Our optimization objective is to minimize a convex combination of these two criteria. If no holes in the shortcut hull are allowed, the problem admits a straight-forward solution via computation of shortest paths. For the more challenging case in which the shortcut hull may contain holes, we present a polynomial-time algorithm that is based on computing a constrained, weighted triangulation of the input polygon's exterior. We use this problem as a starting point for investigating further variants, e.g., restricting the number of edges or bends. We demonstrate that shortcut hulls can be used for the schematization of polygons.}, author = {Annika Bonerath and Jan-Henrik Haunert and Joseph S.B. Mitchell and Benjamin Niedermann}, doi = {https://doi.org/10.1016/j.comgeo.2023.101983}, issn = {0925-7721}, journal = {Computational Geometry Theory and Applications}, pages = {101983}, title = {Shortcut Hulls: Vertex-restricted Outer Simplifications of Polygons}, url = {https://www.sciencedirect.com/science/article/pii/S0925772123000032}, year = {2023} }

	Youness Dehbi, Julius Knechtel, Benjamin Niedermann, and Jan-Henrik Haunert. Incremental constraint-based reasoning for estimating as-built electric line routing in buildings. Automation in Construction, 143:104571, 2022. abstract doi bibtex
	This article addresses the augmentation of existing building models by a-priori not observable structures such as electric installations. The aim is to unambiguously determine an electric network in an incremental manner with a minimum number of local measurements, e.g. using wire detectors, by suggesting the next measurement. Different reasoning strategies, e.g. utilizing graph-theoretical algorithms, have been presented and tested based on a hypothesis which is generated using Mixed Integer Linear Programming (MILP) while incorporating standards regarding the installation of electric wiring and findings from previous measurements. The presented method has been successfully applied on simulated and real-world buildings, it saves up to 80% of the necessary measurements compared to an exhaustive verification of the whole existing electric network, and paves the way for efficiently extending existing models, e.g. GIS models, with information on hidden utilities. This opens up new opportunities to model further infrastructures, e.g. water pipes, in future research. doi:10.1016/j.autcon.2022.104571 @article{dehbi2022incrementalConstraint-based, abstract = {This article addresses the augmentation of existing building models by a-priori not observable structures such as electric installations. The aim is to unambiguously determine an electric network in an incremental manner with a minimum number of local measurements, e.g. using wire detectors, by suggesting the next measurement. Different reasoning strategies, e.g. utilizing graph-theoretical algorithms, have been presented and tested based on a hypothesis which is generated using Mixed Integer Linear Programming (MILP) while incorporating standards regarding the installation of electric wiring and findings from previous measurements. The presented method has been successfully applied on simulated and real-world buildings, it saves up to 80% of the necessary measurements compared to an exhaustive verification of the whole existing electric network, and paves the way for efficiently extending existing models, e.g. GIS models, with information on hidden utilities. This opens up new opportunities to model further infrastructures, e.g. water pipes, in future research.}, author = {Dehbi, Youness and Knechtel, Julius and Niedermann, Benjamin and Haunert, Jan-Henrik}, doi = {10.1016/j.autcon.2022.104571}, journal = {Automation in Construction}, pages = {104571}, title = {Incremental Constraint-based Reasoning for Estimating As-built Electric Line Routing in Buildings}, volume = {143}, year = {2022} }
	L. Weilian, Z. Jun, J.-H. Haunert, F. Lin, Z. Qing, and Y. Dehbi. Three-dimensional virtual representation for the whole process of dam-break floods from a geospatial storytelling perspective. International Journal of Digital Earth, 15:1637-1656, 2022. abstract doi bibtex
	The objective of disaster scenes is to share location-based risk information to a large audience in an effective and intuitive way. However, current studies on three-dimensional (3D) representation for dam-break floods have the following limitations: (1) they are lacking a reasonable logic to organize the whole process of dam-break floods, (2) they present information in a way that cannot be easily understood by laypersons. Geospatial storytelling helps to create exciting experiences and to explain complex relationships of geospatial phenomena. This article proposes a three-dimensional virtual representation method for the whole process of dam-break floods from a geospatial storytelling perspective. The creation of a storyline and a storytelling-oriented representation of dam-break floods are discussed in detail. Finally, a prototype system based on WebGL is developed to conduct an experiment analysis. The results of the experiment show that the proposed method can effectively support 3D representation of the spatiotemporal process of dam-break floods. Furthermore, the statistical results indicate that the storytelling is useful for assisting participants in understanding the occurrence and development of dam-break floods, and is applicable to the popularization of disaster science for the general public. doi:10.1080/17538947.2022.2118877 @article{li2022storytelling, abstract = {The objective of disaster scenes is to share location-based risk information to a large audience in an effective and intuitive way. However, current studies on three-dimensional (3D) representation for dam-break floods have the following limitations: (1) they are lacking a reasonable logic to organize the whole process of dam-break floods, (2) they present information in a way that cannot be easily understood by laypersons. Geospatial storytelling helps to create exciting experiences and to explain complex relationships of geospatial phenomena. This article proposes a three-dimensional virtual representation method for the whole process of dam-break floods from a geospatial storytelling perspective. The creation of a storyline and a storytelling-oriented representation of dam-break floods are discussed in detail. Finally, a prototype system based on WebGL is developed to conduct an experiment analysis. The results of the experiment show that the proposed method can effectively support 3D representation of the spatiotemporal process of dam-break floods. Furthermore, the statistical results indicate that the storytelling is useful for assisting participants in understanding the occurrence and development of dam-break floods, and is applicable to the popularization of disaster science for the general public.}, author = {Weilian, L. and Jun, Z. and Haunert, J.-H. and Lin, F. and Qing, Z. and Dehbi, Y.}, doi = {10.1080/17538947.2022.2118877}, journal = {International Journal of Digital Earth}, pages = {1637--1656}, title = {Three-dimensional virtual representation for the whole process of dam-break floods from a geospatial storytelling perspective}, volume = {15}, year = {2022} }
	Anna Arutyunova and Anne Driemel and Jan-Henrik Haunert and Herman J. Haverkort and Jürgen Kusche and Elmar Langetepe and Philip Mayer and Petra Mutzel and Heiko Röglin. Minimum-error triangulations for sea surface reconstruction. In volume 224 of LIPIcs. Proc. 38th International Symposium on Computational Geometry (SoCG 2022), pages 7:1-7:18. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022. doi bibtex
	doi:10.4230/LIPIcs.SoCG.2022.7 @inproceedings{arutyunovaDHHKL22, author = {Anna Arutyunova and Anne Driemel and Jan{-}Henrik Haunert and Herman J. Haverkort and J{\"{u}}rgen Kusche and Elmar Langetepe and Philip Mayer and Petra Mutzel and Heiko R{\"{o}}glin}, booktitle = {Proc. 38th International Symposium on Computational Geometry (SoCG 2022)}, doi = {10.4230/LIPIcs.SoCG.2022.7}, pages = {7:1--7:18}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"{u}}r Informatik}, series = {LIPIcs}, title = {Minimum-Error Triangulations for Sea Surface Reconstruction}, url = {https://doi.org/10.4230/LIPIcs.SoCG.2022.7}, volume = {224}, year = {2022} }
	Peter Rottmann, Jan-Henrik Haunert, and Youness Dehbi. Automatic building footprint extraction from 3d laserscans. ISPRS Annals of the Photogrammetry, Remote Sensing and Spatial Information Sciences, X-4/W2-2022:233-240, 2022. abstract doi bibtex
	Building footprints are a prerequisite for many tasks such as urban mapping and planning. Such structures are mostly derived using airborne laser scanning which reveals rather roof structures than the underlying hidden footprint boundary. This paper introduces an approach to extract a 2D building boundary from a 3D point cloud stemming from either terrestrial scanning or via close-range sensing using a mobile platform, e.g. drone. To this end, a pipeline of methods including non-parametric kernel density estimation (KDE) of an underlying probability density function, a solution of the Travelling Salesperson Problem (TSP), outlier elimination and line segmentation are presented to extract the underlying building footprint. KDE turns out to be suitable to automatically determine a horizontal cut in the point cloud. An ordering of the resulting points in this cut using a shortest possible tour based on TSP allows for the application of existing line segmentation algorithms, otherwise dedicated to indoor segmentation. Outliers in the resulting segments are removed using DBSCAN. The segments are then generalized leading to the final footprint geometry. We applied our approach on real-world examples and achieved an IoU between 0.930 and 0.998 assessed by ground truth footprints from both authoritative and VGI data. doi:10.5194/isprs-annals-X-4-W2-2022-233-2022 @article{rottmann2022AutomaticBuilding, abstract = {Building footprints are a prerequisite for many tasks such as urban mapping and planning. Such structures are mostly derived using airborne laser scanning which reveals rather roof structures than the underlying hidden footprint boundary. This paper introduces an approach to extract a 2D building boundary from a 3D point cloud stemming from either terrestrial scanning or via close-range sensing using a mobile platform, e.g. drone. To this end, a pipeline of methods including non-parametric kernel density estimation (KDE) of an underlying probability density function, a solution of the Travelling Salesperson Problem (TSP), outlier elimination and line segmentation are presented to extract the underlying building footprint. KDE turns out to be suitable to automatically determine a horizontal cut in the point cloud. An ordering of the resulting points in this cut using a shortest possible tour based on TSP allows for the application of existing line segmentation algorithms, otherwise dedicated to indoor segmentation. Outliers in the resulting segments are removed using DBSCAN. The segments are then generalized leading to the final footprint geometry. We applied our approach on real-world examples and achieved an IoU between 0.930 and 0.998 assessed by ground truth footprints from both authoritative and VGI data.}, author = {Peter Rottmann and Jan-Henrik Haunert and Youness Dehbi}, doi = {10.5194/isprs-annals-X-4-W2-2022-233-2022}, journal = {ISPRS Annals of the Photogrammetry, Remote Sensing and Spatial Information Sciences}, pages = {233--240}, title = {Automatic Building Footprint extraction from 3D laserscans}, volume = {X-4/W2-2022}, year = {2022} }
	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. bibtex
	@inproceedings{rottmann2022mosaicsets_compcart, address = {Bonn}, author = {Peter Rottmann and Makus Wallinger and Annika Bonerath and Sven Gedicke and Martin Nöllenburg and Jan-Henrik Haunert}, booktitle = {Abstracts of 1st Workshop on Computational Cartography 2022}, month = {may}, title = {{M}osaic{S}ets: {E}mbedding {S}et {S}ystems into {G}rid {G}raphs}, year = {2022} }
	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. abstract doi bibtex
	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. doi:10.1109/TVCG.2022.3209485 @article{rottmann2022mosaicsets, abstract = {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.}, author = {Peter Rottmann and Makus Wallinger and Annika Bonerath and Sven Gedicke and Martin Nöllenburg and Jan-Henrik Haunert}, doi = {10.1109/TVCG.2022.3209485}, journal = {IEEE Transactions on Visualization and Computer Graphics}, number = {1}, pages = {875-885}, publisher = {IEEE}, title = {MosaicSets: Embedding set systems into grid graphs}, volume = {29}, year = {2022} }
	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. doi bibtex
	doi:10.5194/ica-abs-5-96-2022 @article{bonerath2022spatiotemporal, address = {Vienna}, author = {Bonerath, Annika and Temerowski, Lukas and Gedicke, Sven and Haunert, Jan-Henrik}, doi = {10.5194/ica-abs-5-96-2022}, journal = {Abstracts of the ICA}, month = {sep}, pages = {96}, title = {{E}xploring {S}patio-{T}emporal {E}vent {D}ata on a {S}mart {W}atch}, volume = {5}, year = {2022} }
	Victor Korir, Axel Forsch, Youness Dehbi, and Jan-Henrik Haunert. Visualizing the modal split in public transportation networks. Abstracts of the ICA, 5:89, sep 2022. doi bibtex
	doi:10.5194/ica-abs-5-89-2022 @article{korir2022modalsplit, address = {Vienna}, author = {Korir, Victor and Forsch, Axel and Dehbi, Youness and Haunert, Jan-Henrik}, doi = {10.5194/ica-abs-5-89-2022}, journal = {Abstracts of the ICA}, month = {sep}, pages = {89}, title = {Visualizing the Modal Split in Public Transportation Networks}, volume = {5}, year = {2022} }
	Anna Brauer, Ville Mäkinen, Axel Forsch, Juha Oksanen, and Jan-Henrik Haunert. My home is my secret: concealing sensitive locations by context-aware trajectory truncation. International Journal of Geographical Information Science, 36(12):2496-2524, 2022. abstract doi bibtex
	Ever since location-based services and mobile applications collecting data gathered through Global Navigation Satellite System (GNSS) positioning have become popular, concerns about location privacy have been expressed. Research has shown that human trajectory repositories containing sequences of observed locations ordered in time constitute a rich source for analyzing movement patterns, but they can also reveal sensitive personal information, such as a person’s home address. In this paper, we present a mechanism that protects visits to sensitive locations by suppressing revealing parts of trajectories. Our attack model acknowledges that the course of a trajectory, combined with spatial context information, can facilitate privacy breaches even if sensitive locations have been concealed. Thus, we introduce the concept of k-site-unidentifiability, a specialization of k-anonymity, under which a sensitive location cannot be singled out from a group of at least k sites that the trajectory could have visited. In an experimental study, we show that our method is utility-preserving and protects sensitive locations reliably even in sparsely built environments. As it can process each trajectory independently, individuals may also use our mechanism to enhance their privacy before publishing their trajectories. doi:10.1080/13658816.2022.2081694 @article{brauer2022myhome, abstract = {Ever since location-based services and mobile applications collecting data gathered through Global Navigation Satellite System (GNSS) positioning have become popular, concerns about location privacy have been expressed. Research has shown that human trajectory repositories containing sequences of observed locations ordered in time constitute a rich source for analyzing movement patterns, but they can also reveal sensitive personal information, such as a person’s home address. In this paper, we present a mechanism that protects visits to sensitive locations by suppressing revealing parts of trajectories. Our attack model acknowledges that the course of a trajectory, combined with spatial context information, can facilitate privacy breaches even if sensitive locations have been concealed. Thus, we introduce the concept of k-site-unidentifiability, a specialization of k-anonymity, under which a sensitive location cannot be singled out from a group of at least k sites that the trajectory could have visited. In an experimental study, we show that our method is utility-preserving and protects sensitive locations reliably even in sparsely built environments. As it can process each trajectory independently, individuals may also use our mechanism to enhance their privacy before publishing their trajectories.}, author = {Anna Brauer and Ville M\"{a}kinen and Axel Forsch and Juha Oksanen and Jan-Henrik Haunert}, doi = {10.1080/13658816.2022.2081694}, eprint = {https://doi.org/10.1080/13658816.2022.2081694}, journal = {International Journal of Geographical Information Science}, number = {12}, pages = {2496--2524}, publisher = {Taylor \& Francis}, title = {My home is my secret: concealing sensitive locations by context-aware trajectory truncation}, url = {https://doi.org/10.1080/13658816.2022.2081694}, volume = {36}, year = {2022} }
	Axel Forsch, Friederike Amann, and Jan-Henrik Haunert. Visualizing the off-screen evolution of trajectories. KN - Journal of Cartography and Geographic Information, 72(3):201-212, May 2022. abstract doi bibtex
	In the context of volunteered geographic information, large sets of trajectories of humans and animals are collected. Analyzing these trajectories visually is often complicated due to limited display sizes. For instance, when a user chooses a large map scale to inspect the details of a trajectory, only a small part of the trajectory is visible in the map. Therefore, in this article, we present an approach for visualizing the off-screen evolution of trajectories, i.e., their continuation outside of the displayed map. We propose visual cues in the form of glyphs that are displayed at the map's boundary and that consist of one or multiple disk sectors of varying size and opening angle. These glyphs indicate the direction and variability of direction of a trajectory's continuation outside the map frame. We present an algorithm for computing the glyphs efficiently and evaluate them in a user study. The results show that the glyphs are intuitive to understand even without explanation. We further present suggestions for improving the glyph design based on the results. doi:10.1007/s42489-022-00106-6 @article{forsch2022offscreen, abstract = {In the context of volunteered geographic information, large sets of trajectories of humans and animals are collected. Analyzing these trajectories visually is often complicated due to limited display sizes. For instance, when a user chooses a large map scale to inspect the details of a trajectory, only a small part of the trajectory is visible in the map. Therefore, in this article, we present an approach for visualizing the off-screen evolution of trajectories, i.e., their continuation outside of the displayed map. We propose visual cues in the form of glyphs that are displayed at the map's boundary and that consist of one or multiple disk sectors of varying size and opening angle. These glyphs indicate the direction and variability of direction of a trajectory's continuation outside the map frame. We present an algorithm for computing the glyphs efficiently and evaluate them in a user study. The results show that the glyphs are intuitive to understand even without explanation. We further present suggestions for improving the glyph design based on the results.}, author = {Forsch, Axel and Amann, Friederike and Haunert, Jan-Henrik}, day = {18}, doi = {10.1007/s42489-022-00106-6}, issn = {2524-4965}, journal = {KN - Journal of Cartography and Geographic Information}, month = {May}, number = {3}, pages = {201--212}, title = {Visualizing the Off-Screen Evolution of Trajectories}, volume = {72}, year = {2022} }
	Axel Forsch, Ruben Kemna, Elmar Langetepe, and Jan-Henrik Haunert. Morphing of schematized polygons for animated travel-time maps. In 3rd Schematic Mapping Workshop. 2022. Poster abstract. Available at: https://www.ruhr-uni-bochum.de/schematicmapping/papers/smw-fklh.pdf abstract bibtex
	Travel-time maps are an important tool for analyzing the efficacy of public transportation systems. These maps display one or multiple isochrones. An isochrone is a line of equal travel time, which means that reaching any point on it from a given starting point requires the same amount of time. As timetables are usually very irregular over the course of a week, travel-time maps are highly variant with respect to the starting time. Thus, for an extensive analysis of the network, this variance has to be visualized appropriately. One way of doing this is by using a digital map with animated transitions between different isochrones, so called morphs. In this work, we present an algorithm for computing such morphs between isochrones, particularly targeting schematized travel-time maps as they are often used for visualization in the context of public transportation. In our current research, we are optimizing the morphing between two given polygonal lines. In future research we plan to extend the approach to finding the correct polygon correspondences in the given isochrones. @inproceedings{forsch2022morphing, abstract = {Travel-time maps are an important tool for analyzing the efficacy of public transportation systems. These maps display one or multiple isochrones. An isochrone is a line of equal travel time, which means that reaching any point on it from a given starting point requires the same amount of time. As timetables are usually very irregular over the course of a week, travel-time maps are highly variant with respect to the starting time. Thus, for an extensive analysis of the network, this variance has to be visualized appropriately. One way of doing this is by using a digital map with animated transitions between different isochrones, so called morphs. In this work, we present an algorithm for computing such morphs between isochrones, particularly targeting schematized travel-time maps as they are often used for visualization in the context of public transportation. In our current research, we are optimizing the morphing between two given polygonal lines. In future research we plan to extend the approach to finding the correct polygon correspondences in the given isochrones.}, address = {Bochum}, author = {Forsch, Axel and Kemna, Ruben and Langetepe, Elmar and Haunert, Jan-Henrik}, booktitle = {3rd Schematic Mapping Workshop}, month = {apr}, note = {Poster abstract. Available at: https://www.ruhr-uni-bochum.de/schematicmapping/papers/smw-fklh.pdf}, title = {Morphing of Schematized Polygons for Animated Travel-Time Maps}, year = {2022} }
	Julius Knechtel, Lasse Klingbeil, Jan-Henrik Haunert, and Youness Dehbi. Optimal position and path planning for stop-and-go laserscanning for the acquisition of 3d building models. ISPRS Annals of the Photogrammetry, Remote Sensing and Spatial Information Sciences, V-4-2022:129-136, 2022. abstract doi bibtex
	Terrestrial laser scanning has become more and more popular in recent years. The according planning of the standpoint network is a crucial issue influencing the overhead and the resulting point cloud. Fully static approaches are both cost and time extensive, whereas fully kinematic approaches cannot produce the same data quality. Stop-and-go scanning, which combines the strengths of both strategies, represents a good alternative solution. In the scanning process, the standpoint planning is by now mostly a manual process based on expert knowledge and relying on the surveyor's experience. This paper provides a method based on Mixed Integer Linear Programming (MILP) ensuring an optimal placement of scanner standpoints considering all scanner-related constraints (e.g. incidence angle), a full coverage of the scenery, a sufficient overlap for the subsequent registration and an optimal route planning solving a Traveling Salesperson Problem (TSP). This enables the fully automatic application of autonomous systems for providing a complete model while performing a stop-and-go laser scanning, e.g. with the Spot robot from Boston Dynamics. Our pre-computed solution, i.e. standpoints and trajectory, has been evaluated surveying a real-world environment and successfully compared with a precise LoD2 building model of the underlying scene. The performed ICP-based registration issued from our fully automatic pipeline turns out to be a very good and safe alternative of the otherwise laborious target-based registration. doi:10.5194/isprs-annals-V-4-2022-129-2022 @article{knechtel2022OptimalPositionPath, abstract = {Terrestrial laser scanning has become more and more popular in recent years. The according planning of the standpoint network is a crucial issue influencing the overhead and the resulting point cloud. Fully static approaches are both cost and time extensive, whereas fully kinematic approaches cannot produce the same data quality. Stop-and-go scanning, which combines the strengths of both strategies, represents a good alternative solution. In the scanning process, the standpoint planning is by now mostly a manual process based on expert knowledge and relying on the surveyor's experience. This paper provides a method based on Mixed Integer Linear Programming (MILP) ensuring an optimal placement of scanner standpoints considering all scanner-related constraints (e.g. incidence angle), a full coverage of the scenery, a sufficient overlap for the subsequent registration and an optimal route planning solving a Traveling Salesperson Problem (TSP). This enables the fully automatic application of autonomous systems for providing a complete model while performing a stop-and-go laser scanning, e.g. with the Spot robot from Boston Dynamics. Our pre-computed solution, i.e. standpoints and trajectory, has been evaluated surveying a real-world environment and successfully compared with a precise LoD2 building model of the underlying scene. The performed ICP-based registration issued from our fully automatic pipeline turns out to be a very good and safe alternative of the otherwise laborious target-based registration.}, author = {Knechtel, Julius and Klingbeil, Lasse and Haunert, Jan-Henrik and Dehbi, Youness}, doi = {10.5194/isprs-annals-V-4-2022-129-2022}, journal = {ISPRS Annals of the Photogrammetry, Remote Sensing and Spatial Information Sciences}, pages = {129--136}, title = {Optimal position and path planning for stop-and-go laserscanning for the acquisition of 3D building models}, url = {https://www.isprs-ann-photogramm-remote-sens-spatial-inf-sci.net/V-4-2022/129/2022/}, volume = {V-4-2022}, year = {2022} }

	Alina Nitzke, Benjamin Niedermann, Luciana Fenoglio-Marc, Jürgen Kusche, and Jan-Henrik Haunert. Reconstructing the time-variable sea surface from tide gauge records using optimal data-dependent triangulations. Computers & Geosciences, 157:104920, 2021. abstract doi bibtex
	Reconstructions of sea level prior to the satellite altimeter era are usually derived from tide gauge records; however most algorithms for this assume that modes of sea level variability are stationary which is not true over several decades. Here we suggest a method that is based on optimized data-dependent triangulations of the network of gauge stations. Data-dependent triangulations are triangulations of point sets that rely not only on 2D point positions but also on additional data (here: sea surface anomalies). In particular, min-error criteria have been suggested to construct triangulations that approximate a given surface. In this article, we show how data-dependent triangulations with min-error criteria can be used to reconstruct 2D maps of the sea surface anomaly over a longer time period, assuming that anomalies are continuously monitored at a sparse set of stations and, in addition, observations of a control surface is provided over a shorter time period. At the heart of our method is the idea to learn a min-error triangulation based on the control data that is available, and to use the learned triangulation subsequently to compute piece-wise linear surface models for epochs in which only observations from monitoring stations are given. Moreover, we combine our approach of min-error triangulation with k-order Delaunay triangulation to stabilize the triangles geometrically. We show that this approach is in particular advantageous for the reconstruction of the sea surface by combining tide gauge measurements (which are sparse in space but cover a long period back in time) with data of modern satellite altimetry (which have a high spatial resolution but cover only the last decades). We show how to learn a min-error triangulation and a min-error k-order Delaunay triangulation using an exact algorithm based on integer linear programming. We confront our reconstructions against the Delaunay triangulation which had been proposed earlier for sea-surface modeling and find superior quality. With real data for the North Sea we show that the min-error triangulation outperforms the Delaunay method substantially for reconstructions back in time up to 18 years, and the k-order Delaunay min-error triangulation even up to 21 years for k=2. With a running time of less than one second our approach would be applicable to areas with far greater extent than the North Sea. doi:10.1016/j.cageo.2021.104920 @article{Nitzke2021104920, abstract = {Reconstructions of sea level prior to the satellite altimeter era are usually derived from tide gauge records; however most algorithms for this assume that modes of sea level variability are stationary which is not true over several decades. Here we suggest a method that is based on optimized data-dependent triangulations of the network of gauge stations. Data-dependent triangulations are triangulations of point sets that rely not only on 2D point positions but also on additional data (here: sea surface anomalies). In particular, min-error criteria have been suggested to construct triangulations that approximate a given surface. In this article, we show how data-dependent triangulations with min-error criteria can be used to reconstruct 2D maps of the sea surface anomaly over a longer time period, assuming that anomalies are continuously monitored at a sparse set of stations and, in addition, observations of a control surface is provided over a shorter time period. At the heart of our method is the idea to learn a min-error triangulation based on the control data that is available, and to use the learned triangulation subsequently to compute piece-wise linear surface models for epochs in which only observations from monitoring stations are given. Moreover, we combine our approach of min-error triangulation with k-order Delaunay triangulation to stabilize the triangles geometrically. We show that this approach is in particular advantageous for the reconstruction of the sea surface by combining tide gauge measurements (which are sparse in space but cover a long period back in time) with data of modern satellite altimetry (which have a high spatial resolution but cover only the last decades). We show how to learn a min-error triangulation and a min-error k-order Delaunay triangulation using an exact algorithm based on integer linear programming. We confront our reconstructions against the Delaunay triangulation which had been proposed earlier for sea-surface modeling and find superior quality. With real data for the North Sea we show that the min-error triangulation outperforms the Delaunay method substantially for reconstructions back in time up to 18 years, and the k-order Delaunay min-error triangulation even up to 21 years for k=2. With a running time of less than one second our approach would be applicable to areas with far greater extent than the North Sea.}, author = {Alina Nitzke and Benjamin Niedermann and Luciana Fenoglio-Marc and J\"{u}rgen Kusche and Jan-Henrik Haunert}, doi = {10.1016/j.cageo.2021.104920}, issn = {0098-3004}, journal = {Computers \& Geosciences}, keywords = {Historical evolution of sea surfaces, Time-variable sea-surface reconstruction, Data-dependent triangulations, Higher-order Delaunay triangulations, Min-error triangulations, Mathematical programming}, pages = {104920}, title = {Reconstructing the time-variable sea surface from tide gauge records using optimal data-dependent triangulations}, url = {https://www.sciencedirect.com/science/article/pii/S0098300421002107}, volume = {157}, year = {2021} }
	Youness Dehbi, Johannes Leonhardt, Johannes Oehrlein, and Jan-Henrik Haunert. Optimal scan planning with enforced network connectivity for the acquisition of three-dimensional indoor models. ISPRS Journal of Photogrammetry and Remote Sensing, 180:103-116, 2021. abstract doi bibtex
	The positioning of laser scanners for indoor surveying is still a time and cost expensive process. This article proposes an optimization approach for computing an admissible sensor placement with the minimal number of sensor view point positions. The approach facilitates both wall and floor surveying based on a floorplan of the study object. Optimal solutions are calculated by solving an Integer Linear Program that respects manufacturer specifications incorporating constraints such as full coverage. To enable a subsequent co-registration of the scans, a flow-based constraint formulation ensuring the connectivity of the selected positions in an appropriately defined geometric intersection graph is introduced. The method has been evaluated on real-world objects and compared to heuristic methods that have frequently been used for related problems. Our solutions outperform heuristic approaches regarding both running time and the number of TLS stations. In a case study with a larger floorplan of an institute building and with different parameter settings, our method resulted in a solution with at least two stations less compared to a solution generated by an expert. doi:10.1016/j.isprsjprs.2021.07.013 @article{dehbi2021optimalscan, abstract = {The positioning of laser scanners for indoor surveying is still a time and cost expensive process. This article proposes an optimization approach for computing an admissible sensor placement with the minimal number of sensor view point positions. The approach facilitates both wall and floor surveying based on a floorplan of the study object. Optimal solutions are calculated by solving an Integer Linear Program that respects manufacturer specifications incorporating constraints such as full coverage. To enable a subsequent co-registration of the scans, a flow-based constraint formulation ensuring the connectivity of the selected positions in an appropriately defined geometric intersection graph is introduced. The method has been evaluated on real-world objects and compared to heuristic methods that have frequently been used for related problems. Our solutions outperform heuristic approaches regarding both running time and the number of TLS stations. In a case study with a larger floorplan of an institute building and with different parameter settings, our method resulted in a solution with at least two stations less compared to a solution generated by an expert.}, author = {Dehbi, Youness and Leonhardt, Johannes and Oehrlein, Johannes and Haunert, Jan-Henrik}, doi = {10.1016/j.isprsjprs.2021.07.013}, issn = {0924-2716}, journal = {ISPRS Journal of Photogrammetry and Remote Sensing}, pages = {103-116}, title = {Optimal scan planning with enforced network connectivity for the acquisition of three-dimensional indoor models}, url = {https://www.sciencedirect.com/science/article/pii/S0924271621001982}, volume = {180}, year = {2021} }
	Annika Bonerath, Jan-Henrik Haunert, Joseph S. B. Mitchell, and Benjamin Niedermann. Shortcut hulls: vertex-restricted outer simplifications of polygons. In Meng He, and Don Sheehy, editors. Proceedings of the 33rd Canadian Conference on Computational Geometry, pages 12-23. 2021. abstract bibtex
	Let P be a crossing-free polygon and C a set of shortcuts, where each shortcut is a directed straight-line segment connecting two vertices of P. A shortcut hull of P is another crossing-free polygon that encloses P and whose oriented boundary is composed of elements from C. Shortcut hulls find their application in geo-related problems such as the simplification of contour lines. We aim at a shortcut hull that linearly balances the enclosed area and perimeter. If no holes in the shortcut hull are allowed, the problem admits a straight-forward solution via shortest paths. For the more challenging case that the shortcut hull may contain holes, we present a polynomial-time algorithm that is based on computing a constrained, weighted triangulation of the input polygon’s exterior. We use this problem as a starting point for investigating further variants, e.g., restricting the number of edges or bends. We demonstrate that shortcut hulls can be used for drawing the rough extent of point sets as well as for the schematization of polygons. @inproceedings{Haunert2021, abstract = {Let P be a crossing-free polygon and C a set of shortcuts, where each shortcut is a directed straight-line segment connecting two vertices of P. A shortcut hull of P is another crossing-free polygon that encloses P and whose oriented boundary is composed of elements from C. Shortcut hulls find their application in geo-related problems such as the simplification of contour lines. We aim at a shortcut hull that linearly balances the enclosed area and perimeter. If no holes in the shortcut hull are allowed, the problem admits a straight-forward solution via shortest paths. For the more challenging case that the shortcut hull may contain holes, we present a polynomial-time algorithm that is based on computing a constrained, weighted triangulation of the input polygon’s exterior. We use this problem as a starting point for investigating further variants, e.g., restricting the number of edges or bends. We demonstrate that shortcut hulls can be used for drawing the rough extent of point sets as well as for the schematization of polygons.}, author = {Annika Bonerath and Jan-Henrik Haunert and Joseph S. B. Mitchell and Benjamin Niedermann}, booktitle = {Proceedings of the 33rd Canadian Conference on Computational Geometry}, editor = {Meng He and Don Sheehy}, pages = {12-23}, title = {Shortcut Hulls: Vertex-restricted Outer Simplifications of Polygons}, url = {https://projects.cs.dal.ca/cccg2021/wordpress/wp-content/uploads/2021/08/CCCG2021.pdf}, year = {2021} }
	Jan-Henrik Haunert. Interaktive Karten für große Datens\"atze - eine algorithmische und kartographische Herausforderung. In Geoinformationssysteme 2021 - Beiträge zur 8. Münchner GI-Runde, pages 63-64. 2021. doi bibtex
	doi:https://www.geoinfo.uni-bonn.de/publikationen/pdf/Haunert_Abstract_GI-Runde_2021.pdf @inproceedings{Haunert2021, author = {Jan-Henrik Haunert}, booktitle = {Geoinformationssysteme 2021 -- Beitr\"{a}ge zur 8. M\"{u}nchner GI-Runde}, doi = {https://www.geoinfo.uni-bonn.de/publikationen/pdf/Haunert_Abstract_GI-Runde_2021.pdf}, pages = {63--64}, title = {{I}nteraktive {K}arten für große {D}atens\"{a}tze -- eine algorithmische und kartographische {H}erausforderung}, year = {2021} }
	Anna Arutyunova, Anne Driemel, Jan-Henrik Haunert, Herman Haverkort, Petra Mutzel, and Heiko Röglin. Minimum-error triangulation is NP-hard. In Proceedings of the 37th European Workshop on Computational Geometry (EuroCG'21). 2021. abstract bibtex
	Given two sets of points in the plane, $P$ and $R$, with a real-valued function defined on $P ∪R$, we define for any triangulation defined on $P$ the vertical error at the points of $R$ and wish to find a triangulation that minimizes this error. We show that this problem is NP-hard to approximate within any approximation factor. @inproceedings{Arutyunova2021, abstract = {Given two sets of points in the plane, $P$ and $R$, with a real-valued function defined on $P \cup R$, we define for any triangulation defined on $P$ the vertical error at the points of $R$ and wish to find a triangulation that minimizes this error. We show that this problem is NP-hard to approximate within any approximation factor.}, author = {Anna Arutyunova and Anne Driemel and Jan-Henrik Haunert and Herman Haverkort and Petra Mutzel and Heiko R\"{o}glin}, booktitle = {Proceedings of the 37th European Workshop on Computational Geometry (EuroCG'21)}, title = {Minimum-Error Triangulation is {NP}-hard}, year = {2021} }
	Jakob Geiger, Sabine Cornelsen, Jan-Henrik Haunert, Philipp Kindermann, Tamara Mchedlidze, Martin Nöllenburg, Yoshio Okamoto, and Alexander Wolff. ClusterSets: Optimizing planar clusters in categorical point data. Computer Graphics Forum, 0(0):0, 2021. EuroVis 2021 special issue, accepted for publication abstract bibtex
	In geographic data analysis, one is often given point data of different categories (such as facilities of a university categorized by department). Drawing upon recent research on set visualization, we want to visualize category membership by connecting points of the same category with visual links. Existing approaches that follow this path usually insist on connecting all members of a category, which may lead to many crossings and visual clutter. We propose an approach that avoids crossings between connections of different categories completely. Instead of connecting \emphall data points of the same category, we subdivide categories into smaller, local clusters where needed. We do a case study comparing the legibility of drawings produced by our approach and those by existing approaches. In our problem formulation, we are additionally given a graph $G$ on the data points whose edges express some sort of proximity. Our aim is to find a subgraph $G'$ of $G$ with the following properties: (i)~edges connect only data points of the same category, (ii)~no two edges cross, and (iii)~the number of connected components (clusters) is minimized. We then visualize the clusters in~$G'$. For arbitrary graphs, the resulting optimization problem, Cluster Minimization, is NP-hard (even to approximate). Therefore, we introduce two heuristics. We do an extensive benchmark test on real-world data. Comparisons with exact solutions indicate that our heuristics do astonishing well for certain relative-neighborhood graphs. @article{geiger2021, abstract = {In geographic data analysis, one is often given point data of different categories (such as facilities of a university categorized by department). Drawing upon recent research on set visualization, we want to visualize category membership by connecting points of the same category with visual links. Existing approaches that follow this path usually insist on connecting all members of a category, which may lead to many crossings and visual clutter. We propose an approach that avoids crossings between connections of different categories completely. Instead of connecting \emph{all} data points of the same category, we subdivide categories into smaller, local clusters where needed. We do a case study comparing the legibility of drawings produced by our approach and those by existing approaches. In our problem formulation, we are additionally given a graph $G$ on the data points whose edges express some sort of proximity. Our aim is to find a subgraph $G'$ of $G$ with the following properties: (i)~edges connect only data points of the same category, (ii)~no two edges cross, and (iii)~the number of connected components (clusters) is minimized. We then visualize the clusters in~$G'$. For arbitrary graphs, the resulting optimization problem, Cluster Minimization, is NP-hard (even to approximate). Therefore, we introduce two heuristics. We do an extensive benchmark test on real-world data. Comparisons with exact solutions indicate that our heuristics do astonishing well for certain relative-neighborhood graphs.}, author = {Jakob Geiger and Sabine Cornelsen and Jan-Henrik Haunert and Philipp Kindermann and Tamara Mchedlidze and Martin N\"{o}llenburg and Yoshio Okamoto and Alexander Wolff}, journal = {Computer Graphics Forum}, note = {EuroVis 2021 special issue, accepted for publication}, number = {0}, pages = {0}, title = {{ClusterSets}: {O}ptimizing Planar Clusters in Categorical Point Data}, volume = {0}, year = {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. abstract doi bibtex
	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. doi:10.1080/15230406.2020.1851613 @article{GedickeCaGIS2021, abstract = {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.}, author = {Sven Gedicke and Johannes Oehrlein and Jan-Henrik Haunert}, doi = {10.1080/15230406.2020.1851613}, journal = {Cartography and Geographic Information Science}, number = {2}, pages = {124--139}, title = {Aggregating land-use polygons considering line features as separating map elements}, volume = {48}, year = {2021} }
	Sujoy Bhore, Jan-Henrik Haunert, Fabian Klute, Guangping Li, and Martin Nöllenburg. Balanced independent and dominating sets on colored interval graphs. In Proc. 47th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2021), pages 89-103. Springer International Publishing, 2021. abstract doi bibtex
	We study two new versions of independent and dominating set problems on vertex-colored interval graphs, namely f-Balanced Independent Set (f-BIS) and f-Balanced Dominating Set (f-BDS). Let \$\$G=(V,E)\$\$G=(V,E)be an interval graph with a color assignment function \$\$\\\backslash,\backslashmathrm\\backslashgamma \\backslash,\\:V \backslashrightarrow \backslash\1,\backslashldots ,k\backslash\\$\$$\gamma$:V\textrightarrow\1,\ldots,k\that maps all vertices in G onto k colors. A subset of vertices \$\$S\backslashsubseteq V\$\$S⊆Vis called f-balanced if S contains f vertices from each color class. In the f-BIS and f-BDS problems, the objective is to compute an independent set or a dominating set that is f-balanced. We show that both problems are NP-complete even on proper interval graphs. For the BIS problem on interval graphs, we design two FPT algorithms, one parameterized by (f, k) and the other by the vertex cover number of G. Moreover, for an optimization variant of BIS on interval graphs, we present a polynomial time approximation scheme (PTAS) and an \$\$O(n\backslashlog n)\$\$O(nlogn)time 2-approximation algorithm. doi:10.1007/978-3-030-67731-2_7 @inproceedings{Bhore2021, abstract = {We study two new versions of independent and dominating set problems on vertex-colored interval graphs, namely f-Balanced Independent Set (f-BIS) and f-Balanced Dominating Set (f-BDS). Let {\$}{\$}G=(V,E){\$}{\$}G=(V,E)be an interval graph with a color assignment function {\$}{\$}{\{}{\{}{\backslash},{\backslash}mathrm{\{}{\backslash}gamma {\}}{\backslash},{\}}{\}}:V {\backslash}rightarrow {\backslash}{\{}1,{\backslash}ldots ,k{\backslash}{\}}{\$}{\$}$\gamma$:V{\textrightarrow}{\{}1,{\ldots},k{\}}that maps all vertices in G onto k colors. A subset of vertices {\$}{\$}S{\backslash}subseteq V{\$}{\$}S⊆Vis called f-balanced if S contains f vertices from each color class. In the f-BIS and f-BDS problems, the objective is to compute an independent set or a dominating set that is f-balanced. We show that both problems are NP-complete even on proper interval graphs. For the BIS problem on interval graphs, we design two FPT algorithms, one parameterized by (f, k) and the other by the vertex cover number of G. Moreover, for an optimization variant of BIS on interval graphs, we present a polynomial time approximation scheme (PTAS) and an {\$}{\$}O(n{\backslash}log n){\$}{\$}O(nlogn)time 2-approximation algorithm.}, address = {Cham}, author = {Bhore, Sujoy and Haunert, Jan-Henrik and Klute, Fabian and Li, Guangping and N{\"o}llenburg, Martin}, booktitle = {Proc. 47th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2021)}, doi = {10.1007/978-3-030-67731-2_7}, isbn = {978-3-030-67731-2}, pages = {89--103}, publisher = {Springer International Publishing}, title = {Balanced Independent and Dominating Sets on Colored Interval Graphs}, year = {2021} }
	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 abstract doi bibtex
	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. doi:10.1109/TVCG.2020.3030399 @article{gbnh-zm-21, abstract = {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.}, author = {Gedicke, Sven and Bonerath, Annika and Niedermann, Benjamin and Haunert, Jan-Henrik}, doi = {10.1109/TVCG.2020.3030399}, journal = {IEEE Transactions on Visualization and Computer Graphics}, note = {https://youtu.be/IuMhk8jp54c}, number = {2}, pages = {1247--1256}, title = {{Z}oomless {M}aps: {E}xternal {L}abeling {M}ethods for the {I}nteractive {E}xploration of {D}ense {P}oint {S}ets at a {F}ixed {M}ap {S}cale}, volume = {27}, year = {2021} }
	J.-H. Haunert, D. Schmidt, and M. Schmidt. Anonymization via clustering of locations in road networks (short paper). In Proc. 11th International Conference on Geographic Information Science (GIScience '21). 2021. abstract doi bibtex
	Data related to households or addresses needs be published in an aggregated form to obfuscate sensitive information about individuals. Usually, the data is aggregated to the level of existing administrative zones, but these often do not correspond to formal models of privacy or a desired level of anonymity. Therefore, automatic privacy-preserving spatial clustering methods are needed. To address this need, we present algorithms to partition a given set of locations into $k$-anonymous clusters, meaning that each cluster contains at least $k$ locations. We assume that the locations are given as a set $T ⊆V$ of terminals in a weighted graph $G = (V, E)$ representing a road network. Our approach is to compute a forest in $G$, i.e., a set of trees, each of which corresponds to a cluster. We ensure the $k$-anonymity of the clusters by constraining the trees to span at least $k$ terminals each (plus an arbitrary number of non-terminal nodes called Steiner nodes). By minimizing the total edge weight of the forest, we ensure that the clusters reflect the proximity among the locations. Although the problem is NP-hard, we were able to solve instances of several hundreds of terminals using integer linear programming. Moreover, we present an efficient approximation algorithm and show that it can be used to process large and fine-grained data sets. doi:10.25436/E2CC7P @inproceedings{haunert2021anonymization, abstract = {Data related to households or addresses needs be published in an aggregated form to obfuscate sensitive information about individuals. Usually, the data is aggregated to the level of existing administrative zones, but these often do not correspond to formal models of privacy or a desired level of anonymity. Therefore, automatic privacy-preserving spatial clustering methods are needed. To address this need, we present algorithms to partition a given set of locations into $k$-anonymous clusters, meaning that each cluster contains at least $k$ locations. We assume that the locations are given as a set $T \subseteq V$ of terminals in a weighted graph $G = (V, E)$ representing a road network. Our approach is to compute a forest in $G$, i.e., a set of trees, each of which corresponds to a cluster. We ensure the $k$-anonymity of the clusters by constraining the trees to span at least $k$ terminals each (plus an arbitrary number of non-terminal nodes called Steiner nodes). By minimizing the total edge weight of the forest, we ensure that the clusters reflect the proximity among the locations. Although the problem is NP-hard, we were able to solve instances of several hundreds of terminals using integer linear programming. Moreover, we present an efficient approximation algorithm and show that it can be used to process large and fine-grained data sets.}, author = {Haunert, J.-H. and Schmidt, D. and Schmidt, M.}, booktitle = {Proc. 11th International Conference on Geographic Information Science (GIScience '21)}, doi = {10.25436/E2CC7P}, title = {Anonymization via Clustering of Locations in Road Networks (Short Paper)}, year = {2021} }
	Peter Rottmann, Anne Driemel, Herman Haverkort, Heiko Röglin, and Jan-Henrik Haunert. Bicriteria aggregation of polygons via graph cuts. In Krzysztof Janowicz, and Judith A. Verstegen, editors, volume 208 of Leibniz International Proceedings in Informatics (LIPIcs). 11th International Conference on Geographic Information Science (GIScience 2021) - Part II, pages 6:1-6:16. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021. abstract doi bibtex
	We present a new method for the task of detecting groups of polygons in a given geographic data set and computing a representative polygon for each group. This task is relevant in map generalization where the aim is to derive a less detailed map from a given map. Following a classical approach, we define the output polygons by merging the input polygons with a set of triangles that we select from a constrained Delaunay triangulation of the input polygons' exterior. The innovation of our method is to compute the selection of triangles by solving a bicriteria optimization problem. While on the one hand we aim at minimizing the total area of the outputs polygons, we aim on the other hand at minimizing their total perimeter. We combine these two objectives in a weighted sum and study two computational problems that naturally arise. In the first problem, the parameter that balances the two objectives is fixed and the aim is to compute a single optimal solution. In the second problem, the aim is to compute a set containing an optimal solution for every possible value of the parameter. We present efficient algorithms for these problems based on computing a minimum cut in an appropriately defined graph. Moreover, we show how the result set of the second problem can be approximated with few solutions. In an experimental evaluation, we finally show that the method is able to derive settlement areas from building footprints that are similar to reference solutions. doi:10.4230/LIPIcs.GIScience.2021.II.6 @inproceedings{rottmann2021bicriteria, abstract = {We present a new method for the task of detecting groups of polygons in a given geographic data set and computing a representative polygon for each group. This task is relevant in map generalization where the aim is to derive a less detailed map from a given map. Following a classical approach, we define the output polygons by merging the input polygons with a set of triangles that we select from a constrained Delaunay triangulation of the input polygons' exterior. The innovation of our method is to compute the selection of triangles by solving a bicriteria optimization problem. While on the one hand we aim at minimizing the total area of the outputs polygons, we aim on the other hand at minimizing their total perimeter. We combine these two objectives in a weighted sum and study two computational problems that naturally arise. In the first problem, the parameter that balances the two objectives is fixed and the aim is to compute a single optimal solution. In the second problem, the aim is to compute a set containing an optimal solution for every possible value of the parameter. We present efficient algorithms for these problems based on computing a minimum cut in an appropriately defined graph. Moreover, we show how the result set of the second problem can be approximated with few solutions. In an experimental evaluation, we finally show that the method is able to derive settlement areas from building footprints that are similar to reference solutions.}, address = {Dagstuhl, Germany}, annote = {Keywords: map generalization, aggregation, graph cuts, bicriteria optimization}, author = {Peter Rottmann and Anne Driemel and Herman Haverkort and Heiko R{\"o}glin and Jan-Henrik Haunert}, booktitle = {11th International Conference on Geographic Information Science (GIScience 2021) - Part II}, doi = {10.4230/LIPIcs.GIScience.2021.II.6}, editor = {Janowicz, Krzysztof and Verstegen, Judith A.}, isbn = {978-3-95977-208-2}, issn = {1868-8969}, pages = {6:1--6:16}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, title = {Bicriteria Aggregation of Polygons via Graph Cuts}, url = {https://drops.dagstuhl.de/opus/volltexte/2021/14765}, urn = {urn:nbn:de:0030-drops-147658}, volume = {208}, year = {2021} }
	Timon Behr, Thomas C. van Dijk, Axel Forsch, Jan-Henrik Haunert, and Sabine Storandt. Map matching for semi-restricted trajectories. In Krzysztof Janowicz, and Judith A. Verstegen, editors, volume 208 of Leibniz International Proceedings in Informatics (LIPIcs). Proc. 11th International Conference on Geographic Information Science (GIScience '21) - Part II, pages 12:1-12:16. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021. abstract doi bibtex
	We consider the problem of matching trajectories to a road map, giving particular consideration to trajectories that do not exclusively follow the underlying network. Such trajectories arise, for example, when a person walks through the inner part of a city, crossing market squares or parking lots. We call such trajectories semi-restricted. Sensible map matching of semi-restricted trajectories requires the ability to differentiate between restricted and unrestricted movement. We develop in this paper an approach that efficiently and reliably computes concise representations of such trajectories that maintain their semantic characteristics. Our approach utilizes OpenStreetMap data to not only extract the network but also areas that allow for free movement (as e.g. parks) as well as obstacles (as e.g. buildings). We discuss in detail how to incorporate this information in the map matching process, and demonstrate the applicability of our method in an experimental evaluation on real pedestrian and bicycle trajectories. doi:10.4230/LIPIcs.GIScience.2021.II.12 @inproceedings{behr2021matching, abstract = {We consider the problem of matching trajectories to a road map, giving particular consideration to trajectories that do not exclusively follow the underlying network. Such trajectories arise, for example, when a person walks through the inner part of a city, crossing market squares or parking lots. We call such trajectories semi-restricted. Sensible map matching of semi-restricted trajectories requires the ability to differentiate between restricted and unrestricted movement. We develop in this paper an approach that efficiently and reliably computes concise representations of such trajectories that maintain their semantic characteristics. Our approach utilizes OpenStreetMap data to not only extract the network but also areas that allow for free movement (as e.g. parks) as well as obstacles (as e.g. buildings). We discuss in detail how to incorporate this information in the map matching process, and demonstrate the applicability of our method in an experimental evaluation on real pedestrian and bicycle trajectories.}, address = {Dagstuhl, Germany}, annote = {Keywords: map matching, OpenStreetMap, GPS, trajectory, road network}, author = {Behr, Timon and van Dijk, Thomas C. and Forsch, Axel and Haunert, Jan-Henrik and Storandt, Sabine}, booktitle = {Proc. 11th International Conference on Geographic Information Science (GIScience '21) - Part II}, doi = {10.4230/LIPIcs.GIScience.2021.II.12}, editor = {Janowicz, Krzysztof and Verstegen, Judith A.}, isbn = {978-3-95977-208-2}, issn = {1868-8969}, pages = {12:1--12:16}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, title = {{Map Matching for Semi-Restricted Trajectories}}, url = {https://drops.dagstuhl.de/opus/volltexte/2021/14771}, urn = {urn:nbn:de:0030-drops-147717}, volume = {208}, year = {2021} }
	Axel Forsch, Youness Dehbi, Benjamin Niedermann, Johannes Oehrlein, Peter Rottmann, and Jan-Henrik Haunert. Multimodal travel-time maps with formally correct and schematic isochrones. Transactions in GIS, 25(6):3233-3256, 2021. abstract doi bibtex
	The automatic generation of travel-time maps is a prerequisite for many fields of application such as tourist assistance and spatial decision support systems. The task is to determine outlines of zones that are reachable from a user's location in a given amount of time. In this work, we focus on travel-time maps with a formally guaranteed separation property in the sense that a zone exactly contains the part of the road network that is reachable within a pre-defined time from a given starting point and start time. In contrast to other automated methods, our approach generates schematized travel-time maps that reduce the visual complexity by representing each zone by an octilinear polygon. We aim at octilinear polygons with a small number of bends to further optimize the legibility of the map. The reachable parts of the road network are determined by the integration of timetable information for different modes of public transportation and pedestrian walkways based on a multi-modal time-expanded network. Moreover, the generated travel-time maps visualize multiple travel times using a map overlay of different time zones. In experiments on real-world data we compare our schematic visualizations to travel-time maps created with other visualization techniques. doi:10.1111/tgis.12821 @article{forsch2021isochrones, abstract = {The automatic generation of travel-time maps is a prerequisite for many fields of application such as tourist assistance and spatial decision support systems. The task is to determine outlines of zones that are reachable from a user's location in a given amount of time. In this work, we focus on travel-time maps with a formally guaranteed separation property in the sense that a zone exactly contains the part of the road network that is reachable within a pre-defined time from a given starting point and start time. In contrast to other automated methods, our approach generates schematized travel-time maps that reduce the visual complexity by representing each zone by an octilinear polygon. We aim at octilinear polygons with a small number of bends to further optimize the legibility of the map. The reachable parts of the road network are determined by the integration of timetable information for different modes of public transportation and pedestrian walkways based on a multi-modal time-expanded network. Moreover, the generated travel-time maps visualize multiple travel times using a map overlay of different time zones. In experiments on real-world data we compare our schematic visualizations to travel-time maps created with other visualization techniques.}, author = {Forsch, Axel and Dehbi, Youness and Niedermann, Benjamin and Oehrlein, Johannes and Rottmann, Peter and Haunert, Jan-Henrik}, doi = {10.1111/tgis.12821}, journal = {Transactions in GIS}, number = {6}, pages = {3233--3256}, title = {Multimodal Travel-Time Maps with Formally Correct and Schematic Isochrones}, volume = {25}, year = {2021} }
	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. abstract doi bibtex
	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. doi:10.1016/j.cag.2021.07.019 @article{gjnmh-zm-21, abstract = {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.}, author = {Gedicke, S. and Jabrayilov, A. and Niedermann, B. and Mutzel, P. and Haunert, J.-H.}, doi = {10.1016/j.cag.2021.07.019}, issn = {0097-8493}, journal = {Computers & Graphics}, pages = {66-80}, title = {Point feature label placement for multi-page maps on small-screen devices}, url = {https://www.sciencedirect.com/science/article/pii/S0097849321001564}, volume = {100}, year = {2021} }

	A. Bonerath, B. Niedermann, J. Diederich, Y. Orgeig, J. Oehrlein, and J.-H. Haunert. A time-windowed data structure for spatial density maps. In Proc. 28th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM SIGSPATIAL '20), pages 15-24. 2020. abstract doi bibtex
	The visualization of spatio-temporal data helps researchers understand global processes such as animal migration. In particular, interactively restricting the data to different time windows reveals new insights into the short-term and long-term changes of the research data. Inspired by this use case, we consider the visualization of point data annotated with time stamps. We pick up classical, grid-based density maps as the underlying visualization technique and enhance them with an efficient data structure for arbitrarily specified time-window queries. The running time of the queries is logarithmic in the total number of points and linear in the number of actually colored cells. In experiments on real-world data we show that the data structure answers time-window queries within milliseconds, which supports the interactive exploration of large point sets. Further, the data structure can be used to visualize additional decision problems, e.g., it can answer whether the sum or maximum of additional weights given with the points exceed a certain threshold. We have defined the data structure general enough to also support multiple thresholds expressed by different colors. doi:10.1145/3397536.3422242 @inproceedings{bhn-twdssdm-20, abstract = {The visualization of spatio-temporal data helps researchers understand global processes such as animal migration. In particular, interactively restricting the data to different time windows reveals new insights into the short-term and long-term changes of the research data. Inspired by this use case, we consider the visualization of point data annotated with time stamps. We pick up classical, grid-based density maps as the underlying visualization technique and enhance them with an efficient data structure for arbitrarily specified time-window queries. The running time of the queries is logarithmic in the total number of points and linear in the number of actually colored cells. In experiments on real-world data we show that the data structure answers time-window queries within milliseconds, which supports the interactive exploration of large point sets. Further, the data structure can be used to visualize additional decision problems, e.g., it can answer whether the sum or maximum of additional weights given with the points exceed a certain threshold. We have defined the data structure general enough to also support multiple thresholds expressed by different colors.}, author = {Bonerath, A. and Niedermann, B. and Diederich, J. and Orgeig, Y. and Oehrlein, J. and Haunert, J.-H.}, booktitle = {Proc. 28th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM SIGSPATIAL '20)}, doi = {10.1145/3397536.3422242}, pages = {15--24}, title = {{A Time-Windowed Data Structure for Spatial Density Maps}}, year = {2020} }
	Sujoy Bhore, Jan-Henrik Haunert, Fabian Klute, Guangping Li, and Martin Nöllenburg. Balanced independent and dominating sets on colored interval graphs. In Proc. 36th European Workshop on Computational Geometry (EuroCG 2020), pages 66:1-66:6. 2020. abstract bibtex
	We study two new versions of independent and dominating set problems on vertex-colored interval graphs, namely \emph$f$-Balanced Independent Set ($f$-BIS) and \emph$f$-Balanced Dominating Set ($f$-BDS). Let $G=(V,E)$ be a vertex-colored interval graph with a $k$-coloring $γo̧lon V i̊ghtarrow \1,\ldots,k\$ for some $k ∈\mathbb N$. A subset of vertices $S⊆V$ is called \emph$f$-balanced if $S$ contains $f$ vertices from each color class. In the $f$-BIS and $f$-BDS problems, the objective is to compute an independent set or a dominating set that is $f$-balanced. We show that both problems are \NP-complete even on proper interval graphs. For the BIS problem on interval graphs, we design two \FPT\ algorithms, one parameterized by $(f,k)$ and the other by the vertex cover number of $G$. Moreover, we present a 2-approximation algorithm for a slight variation of BIS on proper interval graphs. @inproceedings{BhoreEtAl2020, abstract = {We study two new versions of independent and dominating set problems on vertex-colored interval graphs, namely \emph{$f$-Balanced Independent Set} ($f$-BIS) and \emph{$f$-Balanced Dominating Set} ($f$-BDS). Let $G=(V,E)$ be a vertex-colored interval graph with a $k$-coloring $\gamma \colon V \rightarrow \{1,\ldots,k\}$ for some $k \in \mathbb N$. A subset of vertices $S\subseteq V$ is called \emph{$f$-balanced} if $S$ contains $f$ vertices from each color class. In the $f$-BIS and $f$-BDS problems, the objective is to compute an independent set or a dominating set that is $f$-balanced. We show that both problems are \NP-complete even on proper interval graphs. For the BIS problem on interval graphs, we design two \FPT\ algorithms, one parameterized by $(f,k)$ and the other by the vertex cover number of $G$. Moreover, we present a 2-approximation algorithm for a slight variation of BIS on proper interval graphs.}, author = {Sujoy Bhore and Jan{-}Henrik Haunert and Fabian Klute and Guangping Li and Martin N{\"{o}}llenburg}, booktitle = {Proc. 36th European Workshop on Computational Geometry (EuroCG 2020)}, pages = {66:1--66:6}, title = {Balanced Independent and Dominating Sets on Colored Interval Graphs}, url = {http://www1.pub.informatik.uni-wuerzburg.de/eurocg2020/data/uploads/papers/eurocg20_paper_66.pdf}, year = {2020} }
	Dongliang Peng, Alexander Wollf, and Jan-Henrik Haunert. *Finding optimal sequences for area aggregation: A vs. integer linear programming.** ACM Transactions on Spatial Algorithms and Systems, 7(1):4:1-4:40, 2020. abstract doi bibtex
	To provide users with maps of different scales and to allow them to zoom in and out without losing context, automatic methods for map generalization are needed. We approach this problem for land-cover maps. Given two land-cover maps at two different scales, we want to find a sequence of small incremental changes that gradually transforms one map into the other. We assume that the two input maps consist of polygons each of which belongs to a given land-cover type. Every polygon on the smaller-scale map is the union of a set of adjacent polygons on the larger-scale map. In each step of the computed sequence, the smallest area is merged with one of its neighbors. We do not select that neighbor according to a prescribed rule but compute the whole sequence of pairwise merges at once, based on global optimization. We have proved that this problem is NP-hard. We formalize this optimization problem as that of finding a shortest path in a (very large) graph. We present the A$^$ algorithm and integer linear programming to solve this optimization problem. To avoid long computing times, we allow the two methods to return non-optimal results. In addition, we present a greedy algorithm as a benchmark. We tested the three methods with a dataset of the official German topographic database ATKIS. Our main result is that A$^$ finds optimal aggregation sequences for more instances than the other two methods within a given time frame. doi:10.1145/3409290 @article{Peng2020, abstract = {To provide users with maps of different scales and to allow them to zoom in and out without losing context, automatic methods for map generalization are needed. We approach this problem for land-cover maps. Given two land-cover maps at two different scales, we want to find a sequence of small incremental changes that gradually transforms one map into the other. We assume that the two input maps consist of polygons each of which belongs to a given land-cover type. Every polygon on the smaller-scale map is the union of a set of adjacent polygons on the larger-scale map. In each step of the computed sequence, the smallest area is merged with one of its neighbors. We do not select that neighbor according to a prescribed rule but compute the whole sequence of pairwise merges at once, based on global optimization. We have proved that this problem is NP-hard. We formalize this optimization problem as that of finding a shortest path in a (very large) graph. We present the A$^$ algorithm and integer linear programming to solve this optimization problem. To avoid long computing times, we allow the two methods to return non-optimal results. In addition, we present a greedy algorithm as a benchmark. We tested the three methods with a dataset of the official German topographic database ATKIS. Our main result is that A$^$ finds optimal aggregation sequences for more instances than the other two methods within a given time frame.}, author = {Dongliang Peng and Alexander Wollf and Jan{-}Henrik Haunert}, doi = {10.1145/3409290}, journal = {{ACM} Transactions on Spatial Algorithms and Systems}, number = {1}, pages = {4:1--4:40}, title = {Finding Optimal Sequences for Area Aggregation: {A}* vs. Integer Linear Programming}, volume = {7}, year = {2020} }
	Matan Mor, Johannes Oehrlein, Jan-Henrik Haunert, and Sagi Dalyot. Whom to follow? A comparison of walking routes computed based on social media photos from different types of contributors. In volume 1. Proc. 23rd AGILE Conference on Geographic Information Science (AGILE 2020), pages 16. 2020. abstract doi bibtex
	Since many tourists share the photos they take on social media channels, large collections of tourist attraction photos are easily accessible online. Recent research has dealt with identifying popular places from these photos, as well as computing city tourism routes based on these photo collections. Although current approaches show great potential, many tourism attractions suffer from being overrun by tourists, not least because many tourists are aware of only a few tourism hot spots that are trending. In the worst case, automatic city route recommendations based on social media photos will intensify this issue and disappoint tourists who seek individual experiences. In the best case, however, if individual preferences are appropriately incorporated into the route planning algorithm, more personalized route recommendations will be achieved. In this paper, we suggest distinguishing two different types of photo contributors, namely: first-time visitors who are usually tourists who "follow the crowd" (e.g., to visit the top tourist attractions), and repeated visitors who are usually locals who "don’t follow the crowd" (e.g., to visit photogenic yet less well-known places). This categorization allows the user to decide how to trade the one objective off against the other. We present a novel method based on a classification of photographers into locals and tourists, and show how to incorporate this information into an algorithmic routing framework based on the Orienteering Problem approach. In detailed experiments we analyze how choosing the parameter that models the trade-off between both objectives influences the optimal route found by the algorithm, designed to serve the user’s travel objective and preferences in terms of visited attraction types. doi:10.5194/agile-giss-1-16-2020 @inproceedings{Mor2020, abstract = {Since many tourists share the photos they take on social media channels, large collections of tourist attraction photos are easily accessible online. Recent research has dealt with identifying popular places from these photos, as well as computing city tourism routes based on these photo collections. Although current approaches show great potential, many tourism attractions suffer from being overrun by tourists, not least because many tourists are aware of only a few tourism hot spots that are trending. In the worst case, automatic city route recommendations based on social media photos will intensify this issue and disappoint tourists who seek individual experiences. In the best case, however, if individual preferences are appropriately incorporated into the route planning algorithm, more personalized route recommendations will be achieved. In this paper, we suggest distinguishing two different types of photo contributors, namely: first-time visitors who are usually tourists who "follow the crowd" (e.g., to visit the top tourist attractions), and repeated visitors who are usually locals who "don’t follow the crowd" (e.g., to visit photogenic yet less well-known places). This categorization allows the user to decide how to trade the one objective off against the other. We present a novel method based on a classification of photographers into locals and tourists, and show how to incorporate this information into an algorithmic routing framework based on the Orienteering Problem approach. In detailed experiments we analyze how choosing the parameter that models the trade-off between both objectives influences the optimal route found by the algorithm, designed to serve the user’s travel objective and preferences in terms of visited attraction types.}, author = {Matan Mor and Johannes Oehrlein and Jan-Henrik Haunert and Sagi Dalyot}, booktitle = {Proc. 23rd {AGILE} Conference on Geographic Information Science (AGILE 2020)}, doi = {10.5194/agile-giss-1-16-2020}, pages = {16}, title = {Whom to Follow? {A} Comparison of Walking Routes Computed Based on Social Media Photos from Different Types of Contributors}, volume = {1}, year = {2020} }
	Hansjörg Kutterer, Hans Neuner, Helmut Mayer, Jan-Henrik Haunert, and Alexandra Weitkamp. Forschungsvorhaben. In Klaus Kummer, Theo Kötter, Hansjörg Kutterer, and Stefan Ostrau, editors. Das deutsche Vermessungs- und Geoinformationswesen 2020, pages 1067-1102. Wichmann Verlag, Heidelberg, Germany, 2020. bibtex
	@incollection{Kutterer2020, author = {Hansj\"{o}rg Kutterer and Hans Neuner and Helmut Mayer and Jan-Henrik Haunert and Alexandra Weitkamp}, booktitle = {Das deutsche Vermessungs- und Geoinformationswesen 2020}, chapter = {19}, editor = {Klaus Kummer and Theo K\"{o}tter and Hansj\"{o}rg Kutterer and Stefan Ostrau}, isbn = {978-3-87907-676-5}, pages = {1067--1102}, publisher = {Wichmann Verlag, Heidelberg, Germany}, title = {Forschungsvorhaben}, year = {2020} }
	A. Bonerath, J.-H. Haunert, and B. Niedermann. Tight rectilinear hulls of simple polygons. In Proceedings of the 36th European Workshop on Computational Geometry (EuroCG'20). 2020. trailer: https://youtu.be/GZTS5fs0FG4, presentation: https://youtu.be/B392e75WK2U abstract bibtex
	A polygon is called C-oriented if the orientations of all its edges stem from a pre-defined set C. The schematization of a polygon is then a C-oriented polygon that describes and simplifies the shape of the input polygon with respect to given hard and soft constraints. We study the case that the C-oriented polygon needs to contain the input polygon such that it is tight in the sense that it cannot be shrunk without starting to overlap with the input polygon; we call this a tight C-hull of the polygon. We restrict the tight C-hull to be a simple polygon. We aim at a tight C-hull that optimally balances the number of bends, the total edge length and the enclosed area. For the case that both polygons are rectilinear, we present a dynamic-programming approach that yields such a tight hull in polynomial time. For arbitrary simple polygons we can use the same approach to obtain approximate tight rectilinear hulls. @inproceedings{bhn-trhsp-20, abstract = {A polygon is called C-oriented if the orientations of all its edges stem from a pre-defined set C. The schematization of a polygon is then a C-oriented polygon that describes and simplifies the shape of the input polygon with respect to given hard and soft constraints. We study the case that the C-oriented polygon needs to contain the input polygon such that it is tight in the sense that it cannot be shrunk without starting to overlap with the input polygon; we call this a tight C-hull of the polygon. We restrict the tight C-hull to be a simple polygon. We aim at a tight C-hull that optimally balances the number of bends, the total edge length and the enclosed area. For the case that both polygons are rectilinear, we present a dynamic-programming approach that yields such a tight hull in polynomial time. For arbitrary simple polygons we can use the same approach to obtain approximate tight rectilinear hulls.}, author = {Bonerath, A. and Haunert, J.-H. and Niedermann, B.}, booktitle = {Proceedings of the 36th European Workshop on Computational Geometry (EuroCG'20)}, note = {trailer: https://youtu.be/GZTS5fs0FG4, presentation: https://youtu.be/B392e75WK2U}, title = {{Tight Rectilinear Hulls of Simple Polygons}}, url = {http://www1.pub.informatik.uni-wuerzburg.de/eurocg2020/data/uploads/eurocg20_proceedings.pdf}, year = {2020} }
	A. Bonerath, J.-H. Haunert, and B. Niedermann. Dynamic aggregation of geo-objects for the interactive exploration of research data. In volume 29. Publikationen der Deutschen Gesellschaft für Photogrammetrie, Fernerkundung und Geoinformation e.V., DGPF Jahrestagung 2020, Stuttgart, Germany, pages 488-496. 2020. abstract bibtex
	In the context of research data management, the interactive exploration of data is a useful tool to make data findable and reusable. For exploring spatio- and temporal data we developed in a previously published work a data structure that provides the user with simple visualizations of the data for time window queries. We considered the data to be points in space each associated with a time stamp and we visualized it using \alpha-shapes, which generalize convex hulls. In general, time windowed data structures support time window queries for geometric shapes or more general problems from computational geometry such as counting and intersection problems. With this paper, we contribute a review of our previously published method in the context of time windowed data structures, which is a relatively new concept of computational geometry. In particular, we highlight the relevance of our work for a growing domain of research. @inproceedings{bhn-dagoierd20, abstract = {In the context of research data management, the interactive exploration of data is a useful tool to make data findable and reusable. For exploring spatio- and temporal data we developed in a previously published work a data structure that provides the user with simple visualizations of the data for time window queries. We considered the data to be points in space each associated with a time stamp and we visualized it using \alpha-shapes, which generalize convex hulls. In general, time windowed data structures support time window queries for geometric shapes or more general problems from computational geometry such as counting and intersection problems. With this paper, we contribute a review of our previously published method in the context of time windowed data structures, which is a relatively new concept of computational geometry. In particular, we highlight the relevance of our work for a growing domain of research.}, author = {Bonerath, A. and Haunert, J.-H. and Niedermann, B.}, booktitle = {Publikationen der Deutschen Gesellschaft f\"ur Photogrammetrie, Fernerkundung und Geoinformation e.V., DGPF Jahrestagung 2020, Stuttgart, Germany}, number = {0}, pages = {488--496}, title = {Dynamic Aggregation of Geo-Objects for the Interactive Exploration of Research Data}, volume = {29}, year = {2020} }
	A. Corbin, B. Niedermann, A. Nothnagel, Haas R., and J.-H. Haunert. Combinatorial optimization applied to VLBI scheduling. Journal of Geodesy, 94(19):1-22, 2020. abstract doi bibtex
	Due to the advent of powerful solvers, today linear programming has seen many applications in production and routing. In this publication, we present mixed-integer linear programming as applied to scheduling geodetic very-long-baseline interferometry (VLBI) observations. The approach uses combinatorial optimization and formulates the scheduling task as a mixed-integer linear program. Within this new method, the schedule is considered as an entity containing all possible observations of an observing session at the same time, leading to a global optimum. In our example, the optimum is found by maximizing the sky coverage score. The sky coverage score is computed by a hierarchical partitioning of the local sky above each telescope into a number of cells. Each cell including at least one observation adds a certain gain to the score. The method is computationally expensive and this publication may be ahead of its time for large networks and large numbers of VLBI observations. However, considering that developments of solvers for combinatorial optimization are progressing rapidly and that computers increase in performance, the usefulness of this approach may come up again in some distant future. Nevertheless, readers may be prompted to look into these optimization methods already today seeing that they are available also in the geodetic literature. The validity of the concept and the applicability of the logic are demonstrated by evaluating test schedules for five 1-h, single-baseline Intensive VLBI sessions. Compared to schedules that were produced with the scheduling software sked, the number of observations per session is increased on average by three observations and the simulated precision of UT1-UTC is improved in four out of five cases (6 µs average improvement in quadrature). Moreover, a simplified and thus much faster version of the mixed-integer linear program has been developed for modern VLBI Global Observing System telescopes. doi:10.1007/s00190-020-01348-w @article{cnnhh-coas20, abstract = {Due to the advent of powerful solvers, today linear programming has seen many applications in production and routing. In this publication, we present mixed-integer linear programming as applied to scheduling geodetic very-long-baseline interferometry (VLBI) observations. The approach uses combinatorial optimization and formulates the scheduling task as a mixed-integer linear program. Within this new method, the schedule is considered as an entity containing all possible observations of an observing session at the same time, leading to a global optimum. In our example, the optimum is found by maximizing the sky coverage score. The sky coverage score is computed by a hierarchical partitioning of the local sky above each telescope into a number of cells. Each cell including at least one observation adds a certain gain to the score. The method is computationally expensive and this publication may be ahead of its time for large networks and large numbers of VLBI observations. However, considering that developments of solvers for combinatorial optimization are progressing rapidly and that computers increase in performance, the usefulness of this approach may come up again in some distant future. Nevertheless, readers may be prompted to look into these optimization methods already today seeing that they are available also in the geodetic literature. The validity of the concept and the applicability of the logic are demonstrated by evaluating test schedules for five 1-h, single-baseline Intensive VLBI sessions. Compared to schedules that were produced with the scheduling software sked, the number of observations per session is increased on average by three observations and the simulated precision of UT1-UTC is improved in four out of five cases (6 µs average improvement in quadrature). Moreover, a simplified and thus much faster version of the mixed-integer linear program has been developed for modern VLBI Global Observing System telescopes.}, author = {Corbin, A. and Niedermann, B. and Nothnagel, A. and Haas R. and Haunert, J.-H.}, doi = {10.1007/s00190-020-01348-w}, journal = {Journal of Geodesy}, number = {19}, pages = {1--22}, title = {Combinatorial optimization applied to {VLBI} scheduling}, volume = {94}, year = {2020} }

	B. Niedermann, and J.-H. Haunert. Focus+context map labeling with optimized clutter reduction. International Journal of Cartography, 5(2-3):158-177, 2019. Special issue of 29th International Cartographic Conference (ICC'19) abstract doi bibtex
	Zooming is a basic operation that many digital maps support for exploring them interactively. Especially for maps on small-screen devices this is a helpful operation to uncover the user’s region of interest possibly hidden by labels, e.g., points of interest represented by icons. However, by scaling the map larger the user loses the context. As a consequent the user might need to repeatedly zoom in and out to explore the map step by step. We present an approach that reduces the necessity of zooming by providing the user with the possibility of displacing the labels of a circular focus region. To that end, we utilize techniques from focus+context maps implementing the displacement of the labels by fish-eye projections. The visual association between labels and their point features is established by connecting lines aggregated to bundles. Our approach particularly guarantees that labels move smoothly when the user continuously shifts the focus region, which reduces distracting flickering effects while exploring the map by panning the map view. Further, when the user stops moving the focus region, mathematical programming is applied to optimize positions of the displaced labels. In an evaluation on real-world data and synthetically generated data we show that our approach substantially increases the legibility of both the focus region and the displaced labels doi:10.1080/23729333.2019.1613072 @article{niedermann2019, abstract = {Zooming is a basic operation that many digital maps support for exploring them interactively. Especially for maps on small-screen devices this is a helpful operation to uncover the user’s region of interest possibly hidden by labels, e.g., points of interest represented by icons. However, by scaling the map larger the user loses the context. As a consequent the user might need to repeatedly zoom in and out to explore the map step by step. We present an approach that reduces the necessity of zooming by providing the user with the possibility of displacing the labels of a circular focus region. To that end, we utilize techniques from focus+context maps implementing the displacement of the labels by fish-eye projections. The visual association between labels and their point features is established by connecting lines aggregated to bundles. Our approach particularly guarantees that labels move smoothly when the user continuously shifts the focus region, which reduces distracting flickering effects while exploring the map by panning the map view. Further, when the user stops moving the focus region, mathematical programming is applied to optimize positions of the displaced labels. In an evaluation on real-world data and synthetically generated data we show that our approach substantially increases the legibility of both the focus region and the displaced labels}, author = {Niedermann, B. and Haunert, J.{-}H.}, doi = {10.1080/23729333.2019.1613072}, journal = {International Journal of Cartography}, note = {Special issue of 29th International Cartographic Conference (ICC'19)}, number = {2--3}, pages = {158--177}, publisher = {Taylor & Francis}, title = {Focus+Context Map Labeling with Optimized Clutter Reduction}, volume = {5}, year = {2019} }
	A. Bonerath, J.-H. Haunert, and B. Niedermann. Computing alpha-shapes for temporal range queries on point sets. In Proceedings of the 35rd European Workshop on Computational Geometry (EuroCG'19). 2019. Preprint. abstract bibtex
	The interactive exploration of data requires data structures that can be repeatedly queried to obtain simple visualizations of parts of the data. In this paper we consider the scenario that the data is a set of points each associated with a time stamp and that the result of each query is visualized by an α-shape, which generalizes the concept of convex hulls. Instead of computing each shape independently, we suggest and analyze a simple data structure that aggregates the α-shapes of all possible queries. Once the data structure is built, it particularly allows us to query single α-shapes without retrieving the actual (possibly large) point set and thus to rapidly produce small previews of the queried data. @inproceedings{bhn-castrqps-19, abstract = {The interactive exploration of data requires data structures that can be repeatedly queried to obtain simple visualizations of parts of the data. In this paper we consider the scenario that the data is a set of points each associated with a time stamp and that the result of each query is visualized by an α-shape, which generalizes the concept of convex hulls. Instead of computing each shape independently, we suggest and analyze a simple data structure that aggregates the α-shapes of all possible queries. Once the data structure is built, it particularly allows us to query single α-shapes without retrieving the actual (possibly large) point set and thus to rapidly produce small previews of the queried data.}, author = {Bonerath, A. and Haunert, J.-H. and Niedermann, B.}, booktitle = {Proceedings of the 35rd European Workshop on Computational Geometry (EuroCG'19)}, note = {Preprint.}, title = {{Computing alpha-Shapes for Temporal Range Queries on Point Sets}}, year = {2019} }
	B. Niedermann, and J.-H. Haunert. Anchored metro maps: combining schematic maps with geographic maps for multi-modal navigation. In Schematic Mapping Workshop 2019. 2019. Poster abstract. abstract bibtex
	For conducting navigation tasks in public trans- portation systems, schematic maps (e.g., metro maps) are the first choice, as they reduce the amount of information to a minimum. On the other hand, for navigation tasks in street networks, classical geographic maps are preferable, as they depict the area as accurately as possible. In this work, we create synergies between both types of maps by laying the metro map over the street map. We call those maps anchored metro maps, as we visually attach the metro stations of the metro map to their counterparts on the street map. Currently, we are developing algorithms optimizing the matching between both maps. In future research we plan to use this approach to show that the combination of schematic and geographical maps leads to an improvement for certain navigation tasks. @inproceedings{nh-amm-19, abstract = {For conducting navigation tasks in public trans- portation systems, schematic maps (e.g., metro maps) are the first choice, as they reduce the amount of information to a minimum. On the other hand, for navigation tasks in street networks, classical geographic maps are preferable, as they depict the area as accurately as possible. In this work, we create synergies between both types of maps by laying the metro map over the street map. We call those maps anchored metro maps, as we visually attach the metro stations of the metro map to their counterparts on the street map. Currently, we are developing algorithms optimizing the matching between both maps. In future research we plan to use this approach to show that the combination of schematic and geographical maps leads to an improvement for certain navigation tasks.}, author = {Niedermann, B. and Haunert, J.-H.}, booktitle = {Schematic Mapping Workshop 2019}, note = {Poster abstract.}, title = {Anchored Metro Maps: Combining Schematic Maps with Geographic Maps for Multi-modal Navigation}, year = {2019} }
	A. Bonerath, B. Niedermann, and J.-H. Haunert. Retrieving alpha-shapes and schematic polygonal approximations for sets of points within queried temporal ranges. In Proc. 27th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM SIGSPATIAL '19), pages 249-258. 2019. trailer: https://youtu.be/mlnUDhbMSfQ abstract doi bibtex
	The interactive exploration of data requires data structures that can be repeatedly queried to obtain simple visualizations of parts of the data. We consider the scenario that the data is a set of points each associated with a time stamp and that the result of each query is visualized by an α-shape, which generalizes the concept of convex hulls. Instead of computing each shape independently, we suggest and analyze a simple data structure that aggregates the α-shapes of all possible queries. Once the data structure is built, it particularly allows us to query single α-shapes without retrieving the actual (possibly large) point set and thus to rapidly produce small previews of the queried data. We discuss the data structure for the original α-shapes as well as for a schematized version of α-shapes, which further simplifies the visualization. We evaluate the data structure on real-world data. The experiments indicate linear memory consumption with respect to the number of points, which makes the data structure applicable in practice, although the size is quadratic for a theoretic worst case example. doi:10.1145/3347146.3359087 @inproceedings{bhn-rasspa-19, abstract = {The interactive exploration of data requires data structures that can be repeatedly queried to obtain simple visualizations of parts of the data. We consider the scenario that the data is a set of points each associated with a time stamp and that the result of each query is visualized by an α-shape, which generalizes the concept of convex hulls. Instead of computing each shape independently, we suggest and analyze a simple data structure that aggregates the α-shapes of all possible queries. Once the data structure is built, it particularly allows us to query single α-shapes without retrieving the actual (possibly large) point set and thus to rapidly produce small previews of the queried data. We discuss the data structure for the original α-shapes as well as for a schematized version of α-shapes, which further simplifies the visualization. We evaluate the data structure on real-world data. The experiments indicate linear memory consumption with respect to the number of points, which makes the data structure applicable in practice, although the size is quadratic for a theoretic worst case example.}, author = {Bonerath, A. and Niedermann, B. and Haunert, J.-H.}, booktitle = {Proc. 27th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM SIGSPATIAL '19)}, doi = {10.1145/3347146.3359087}, note = {trailer: https://youtu.be/mlnUDhbMSfQ}, pages = {249--258}, title = {{Retrieving alpha-Shapes and Schematic Polygonal Approximations for Sets of Points within Queried Temporal Ranges}}, year = {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. abstract bibtex
	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, abstract = {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.}, author = {Gedicke, S. and Niedermann, B. and Haunert, J.-H.}, booktitle = {LBS 2019: 15th International Conference on Location Based Services, November 11--13, 2019, Vienna, AT}, title = {{M}ulti-page {L}abeling of {S}mall-screen {M}aps with a {G}raph-coloring {A}pproach}, year = {2019} }
	J. Oehrlein, B. Niedermann, and J.-H. Haunert. Analyzing the supply and detecting spatial patterns of urban green spaces via optimization. Journal of Photogrammetry, Remote Sensing and Geoinformation Science (PFG), 87(4):137-158, 2019. abstract doi bibtex
	Green spaces in urban areas offer great possibilities of recreation, provided that they are easily accessible. Therefore, an ideal city should offer large green spaces close to where its residents live. Although there are several measures for the assessment of urban green spaces, the existing measures usually focus either on the total size of all green spaces or on their accessibility. Hence, in this paper, we present a new methodology for assessing green-space provision and accessibility in an integrated way. The core of our methodology is an algorithm based on linear programming that computes an optimal assignment between residential areas and green spaces. In a basic setting, it assigns green spaces of a prescribed size exclusively to each resident, such that an objective function that, in particular, considers the average distance between residents and assigned green spaces is optimized. We contribute a detailed presentation on how to engineer an assignment-based method, such that it yields plausible results (e.g., by considering distances in the road network) and becomes efficient enough for the analysis of large metropolitan areas (e.g., we were able to process an instance of Berlin with about 130,000 polygons representing green spaces, 18,000 polygons representing residential areas, and 6 million road segments). Furthermore, we show that the optimal assignments resulting from our method enable a subsequent analysis that reveals both interesting global properties of a city as well as spatial patterns. For example, our method allows us to identify neighborhoods with a shortage of green spaces, which will help spatial planners in their decision-making. doi:10.1007/s41064-019-00081-0 @article{oehrlein2019-pfg, abstract = {Green spaces in urban areas offer great possibilities of recreation, provided that they are easily accessible. Therefore, an ideal city should offer large green spaces close to where its residents live. Although there are several measures for the assessment of urban green spaces, the existing measures usually focus either on the total size of all green spaces or on their accessibility. Hence, in this paper, we present a new methodology for assessing green-space provision and accessibility in an integrated way. The core of our methodology is an algorithm based on linear programming that computes an optimal assignment between residential areas and green spaces. In a basic setting, it assigns green spaces of a prescribed size exclusively to each resident, such that an objective function that, in particular, considers the average distance between residents and assigned green spaces is optimized. We contribute a detailed presentation on how to engineer an assignment-based method, such that it yields plausible results (e.g., by considering distances in the road network) and becomes efficient enough for the analysis of large metropolitan areas (e.g., we were able to process an instance of Berlin with about 130,000 polygons representing green spaces, 18,000 polygons representing residential areas, and 6 million road segments). Furthermore, we show that the optimal assignments resulting from our method enable a subsequent analysis that reveals both interesting global properties of a city as well as spatial patterns. For example, our method allows us to identify neighborhoods with a shortage of green spaces, which will help spatial planners in their decision-making.}, author = {Oehrlein, J. and Niedermann, B. and Haunert, J.-H.}, doi = {10.1007/s41064-019-00081-0}, journal = {Journal of Photogrammetry, Remote Sensing and Geoinformation Science (PFG)}, number = {4}, pages = {137--158}, title = {Analyzing the Supply and Detecting Spatial Patterns of Urban Green Spaces via Optimization}, volume = {87}, year = {2019} }

	B. Niedermann, and J.-H. Haunert. An algorithmic framework for labeling network maps. Algorithmica, 80(5):1493-1533, 2018. abstract doi bibtex
	Drawing network maps automatically comprises two challenging steps, namely laying out the map and placing non-overlapping labels. In this paper we tackle the problem of labeling an already existing network map considering the application of metro maps. We present a flexible and versatile labeling model. Despite its simplicity, we prove that it is NP-complete to label a single line of the network. For a restricted variant of that model, we introduce an efficient algorithm that optimally labels a single line. Based on that algorithm, we present a general and sophisticated workflow for multiple metro lines, which is experimentally evaluated on real-world metro maps. doi:10.1007/s00453-017-0350-0 @article{HaunertN15a, abstract = {Drawing network maps automatically comprises two challenging steps, namely laying out the map and placing non-overlapping labels. In this paper we tackle the problem of labeling an already existing network map considering the application of metro maps. We present a flexible and versatile labeling model. Despite its simplicity, we prove that it is NP-complete to label a single line of the network. For a restricted variant of that model, we introduce an efficient algorithm that optimally labels a single line. Based on that algorithm, we present a general and sophisticated workflow for multiple metro lines, which is experimentally evaluated on real-world metro maps.}, author = {Niedermann, B. and Haunert, J.{-}H.}, doi = {10.1007/s00453-017-0350-0}, journal = {Algorithmica}, number = {5}, pages = {1493--1533}, title = {An Algorithmic Framework for Labeling Network Maps}, volume = {80}, year = {2018} }
	B. Niedermann, J. Oehrlein, S. Lautenbach, and J.-H. Haunert. A network flow model for the analysis of green spaces in urban areas. In volume 114 of Leibniz International Proceedings in Informatics (LIPIcs). Proc. 10th International Conference on Geographic Information Science (GIScience '18), pages 13:1-13:16. 2018. abstract doi bibtex
	Green spaces in urban areas offer great possibilities of recreation, provided that they are easily accessible. Therefore, an ideal city should offer large green spaces close to where its residents live. Although there are several measures for the assessment of urban green spaces, the existing measures usually focus either on the total size of green spaces or on their accessibility. Hence, in this paper, we present a new methodology for assessing green-space provision and accessibility in an integrated way. The core of our methodology is an algorithm based on linear programming that computes an optimal assignment between residential areas and green spaces. In a basic setting, it assigns a green space of a prescribed size exclusively to each resident such that the average distance between residents and assigned green spaces is minimized. We contribute a detailed presentation on how to engineer an assignment-based method such that it yields reasonable results (e.g., by considering distances in the road network) and becomes efficient enough for the analysis of large metropolitan areas (e.g., we were able to process an instance of Berlin with about 130000 polygons representing green spaces, 18000 polygons representing residential areas, and 6 million road segments). Furthermore, we show that the optimal assignments resulting from our method enable a subsequent analysis that reveals both interesting global properties of a city as well as spatial patterns. For example, our method allows us to identify neighborhoods with a shortage of green spaces, which will help spatial planners in their decision making. doi:10.4230/LIPIcs.GISCIENCE.2018.13 @inproceedings{NiedermannEtAl2018, abstract = {Green spaces in urban areas offer great possibilities of recreation, provided that they are easily accessible. Therefore, an ideal city should offer large green spaces close to where its residents live. Although there are several measures for the assessment of urban green spaces, the existing measures usually focus either on the total size of green spaces or on their accessibility. Hence, in this paper, we present a new methodology for assessing green-space provision and accessibility in an integrated way. The core of our methodology is an algorithm based on linear programming that computes an optimal assignment between residential areas and green spaces. In a basic setting, it assigns a green space of a prescribed size exclusively to each resident such that the average distance between residents and assigned green spaces is minimized. We contribute a detailed presentation on how to engineer an assignment-based method such that it yields reasonable results (e.g., by considering distances in the road network) and becomes efficient enough for the analysis of large metropolitan areas (e.g., we were able to process an instance of Berlin with about 130000 polygons representing green spaces, 18000 polygons representing residential areas, and 6 million road segments). Furthermore, we show that the optimal assignments resulting from our method enable a subsequent analysis that reveals both interesting global properties of a city as well as spatial patterns. For example, our method allows us to identify neighborhoods with a shortage of green spaces, which will help spatial planners in their decision making.}, author = {Niedermann, B. and Oehrlein, J. and Lautenbach, S. and Haunert, J.-H.}, booktitle = {Proc. 10th International Conference on Geographic Information Science (GIScience '18)}, doi = {10.4230/LIPIcs.GISCIENCE.2018.13}, pages = {13:1--13:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, title = {A network flow model for the analysis of green spaces in urban areas}, volume = {114}, year = {2018} }
	J. Oehrlein, A. Förster, D. Schunck, Y. Dehbi, R. Roscher, and J.-H. Haunert. Inferring routing preferences of bicyclists from sparse sets of trajectories. In volume IV-4/W7 of ISPRS Annals of the Photogrammetry, Remote Sensing and Spatial Information Sciences. Proc. 3rd International Conference on Smart Data and Smart Cities, pages 107-114. 2018. abstract doi bibtex
	Understanding the criteria that bicyclists apply when they choose their routes is crucial for planning new bicycle paths or recommending routes to bicyclists. This is becoming more and more important as city councils are becoming increasingly aware of limitations of the transport infrastructure and problems related to automobile traffic. Since different groups of cyclists have different preferences, however, searching for a single set of criteria is prone to failure. Therefore, in this paper, we present a new approach to classify trajectories recorded and shared by bicyclists into different groups and, for each group, to identify favored and unfavored road types. Based on these results we show how to assign weights to the edges of a graph representing the road network such that minimumweight paths in the graph, which can be computed with standard shortest-path algorithms, correspond to adequate routes. Our method combines known algorithms for machine learning and the analysis of trajectories in an innovative way and, thereby, constitutes a new comprehensive solution for the problem of deriving routing preferences from initially unclassified trajectories. An important property of our method is that it yields reasonable results even if the given set of trajectories is sparse in the sense that it does not cover all segments of the cycle network. doi:10.5194/isprs-annals-IV-4-W7-107-2018 @inproceedings{OehrleinEtAl2018, abstract = {Understanding the criteria that bicyclists apply when they choose their routes is crucial for planning new bicycle paths or recommending routes to bicyclists. This is becoming more and more important as city councils are becoming increasingly aware of limitations of the transport infrastructure and problems related to automobile traffic. Since different groups of cyclists have different preferences, however, searching for a single set of criteria is prone to failure. Therefore, in this paper, we present a new approach to classify trajectories recorded and shared by bicyclists into different groups and, for each group, to identify favored and unfavored road types. Based on these results we show how to assign weights to the edges of a graph representing the road network such that minimumweight paths in the graph, which can be computed with standard shortest-path algorithms, correspond to adequate routes. Our method combines known algorithms for machine learning and the analysis of trajectories in an innovative way and, thereby, constitutes a new comprehensive solution for the problem of deriving routing preferences from initially unclassified trajectories. An important property of our method is that it yields reasonable results even if the given set of trajectories is sparse in the sense that it does not cover all segments of the cycle network.}, author = {Oehrlein, J. and Förster, A. and Schunck, D. and Dehbi, Y. and Roscher, R. and Haunert, J.-H.}, booktitle = {Proc. 3rd International Conference on Smart Data and Smart Cities}, doi = {10.5194/isprs-annals-IV-4-W7-107-2018}, pages = {107--114}, series = {ISPRS Annals of the Photogrammetry, Remote Sensing and Spatial Information Sciences}, title = {Inferring Routing Preferences of Bicyclists from Sparse Sets of Trajectories}, volume = {IV-4/W7}, year = {2018} }
	Y. Dehbi, N. Gojayeva, A. R. Pickert, J.-H. Haunert, and L. Plümer. Room shapes and functional uses predicted from sparse data. In volume IV-4:33-40 of ISPRS Annals of the Photogrammetry, Remote Sensing and Spatial Information Sciences. Proc. ISPRS Technical Commission IV Symposium. 2018. abstract doi bibtex
	Many researchers used expensive 3D laser scanning techniques to derive indoor models. Few papers describe the derivation of indoor models based on sparse data such as footprints. They assume that floorplans and rooms are rather rectangular and that information on functional use is given. This paper addresses the automatic learning of a classifier which predicts the functional use of housing rooms. The classification is based on features which are widely available such as room areas and orientation. These features are extracted from an extensive database of annotated rooms. A Bayesian classifier is applied which delivers probabilities of competing class hypotheses. In a second step, functional uses are used to predict the shape of the rooms in a further classification. doi:10.5194/isprs-annals-IV-4-33-2018 @inproceedings{DehbiEtAl2018, abstract = {Many researchers used expensive 3D laser scanning techniques to derive indoor models. Few papers describe the derivation of indoor models based on sparse data such as footprints. They assume that floorplans and rooms are rather rectangular and that information on functional use is given. This paper addresses the automatic learning of a classifier which predicts the functional use of housing rooms. The classification is based on features which are widely available such as room areas and orientation. These features are extracted from an extensive database of annotated rooms. A Bayesian classifier is applied which delivers probabilities of competing class hypotheses. In a second step, functional uses are used to predict the shape of the rooms in a further classification.}, author = {Dehbi, Y. and Gojayeva, N. and Pickert, A. R. and Haunert, J.-H. and Pl\"{u}mer, L.}, booktitle = {Proc. ISPRS Technical Commission IV Symposium}, doi = {10.5194/isprs-annals-IV-4-33-2018}, series = {ISPRS Annals of the Photogrammetry, Remote Sensing and Spatial Information Sciences}, title = {Room shapes and functional uses predicted from sparse data}, volume = {IV-4:33--40}, year = {2018} }

	T. C. van Dijk, J.-H Haunert, and J. Oehrlein. Location-dependent generalization of road networks based on equivalent destinations. Computer Graphics Forum, 35(3):451-460, 2016. abstract doi bibtex
	Suppose a user located at a certain vertex in a road network wants to plan a route using a wayfinding map. The user's exact destination may be irrelevant for planning most of the route, because many destinations will be equivalent in the sense that they allow the user to choose almost the same paths. We propose a method to find such groups of destinations automatically and to contract the resulting clusters in a detailed map to achieve a simplified visualization. We model the problem as a clustering problem in rooted, edge-weighted trees. Two vertices are allowed to be in the same cluster if and only if they share at least a given fraction of their path to the root. We analyze some properties of these clusterings and give a linear-time algorithm to compute the minimum-cardinality clustering. This algorithm may have various other applications in network visualization and graph drawing, but in this paper we apply it specifically to focus-and-context map generalization. When contracting shortest-path trees in a geographic network, the computed clustering additionally provides a constant-factor bound on the detour that results from routing using the generalized network instead of the full network. This is a desirable property for wayfinding maps. doi:10.1111/cgf.12921 @article{vanDijkEtAl2016, abstract = {Suppose a user located at a certain vertex in a road network wants to plan a route using a wayfinding map. The user's exact destination may be irrelevant for planning most of the route, because many destinations will be equivalent in the sense that they allow the user to choose almost the same paths. We propose a method to find such groups of destinations automatically and to contract the resulting clusters in a detailed map to achieve a simplified visualization. We model the problem as a clustering problem in rooted, edge-weighted trees. Two vertices are allowed to be in the same cluster if and only if they share at least a given fraction of their path to the root. We analyze some properties of these clusterings and give a linear-time algorithm to compute the minimum-cardinality clustering. This algorithm may have various other applications in network visualization and graph drawing, but in this paper we apply it specifically to focus-and-context map generalization. When contracting shortest-path trees in a geographic network, the computed clustering additionally provides a constant-factor bound on the detour that results from routing using the generalized network instead of the full network. This is a desirable property for wayfinding maps.}, author = {Dijk, T. C. van and Haunert, J.-H and Oehrlein, J.}, doi = {10.1111/cgf.12921}, journal = {Computer Graphics Forum}, number = {3}, pages = {451{--}460}, title = {Location-dependent generalization of road networks based on equivalent destinations}, volume = {35}, year = {2016} }
	J.-H. Haunert, and A. Wolff. Räumliche analyse durch kombinatorische optimierung. In W. Freeden, and R. Rummel, editors. Handbuch der Geodäsie: 5 Bände, pages 1-39. Springer Berlin Heidelberg, 2016. abstract doi bibtex
	In diesem Beitrag geht es uns darum, an einigen wenigen Beispielen aus der räumlichen Analyse grundlegende Entwurfstechniken für Algorithmen und Werkzeuge der kombinatorischen Optimierung zu illustrieren. AuSSerdem wollen wir ein Minimum an theoretischem Unterbau vermitteln. Damit hoffen wir, dass es dem Leser, der Leserin gelingt, räumliche Probleme mit Methoden der Informatik bewusst und damit erfolgreich zu lösen. Wir halten es für besonders wichtig, dass man neue Probleme sorgfältig mathematisch modelliert und mittels exakter Algorithmen das eigene Modell wenigstens auf kleinen Instanzen überprüft, bevor man sich schnellen Heuristiken zuwendet, um groSSe Instanzen zu lösen. doi:10.1007/978-3-662-46900-2_69-1 @incollection{Haunert2016, abstract = {In diesem Beitrag geht es uns darum, an einigen wenigen Beispielen aus der r{\"a}umlichen Analyse grundlegende Entwurfstechniken f{\"u}r Algorithmen und Werkzeuge der kombinatorischen Optimierung zu illustrieren. AuSSerdem wollen wir ein Minimum an theoretischem Unterbau vermitteln. Damit hoffen wir, dass es dem Leser, der Leserin gelingt, r{\"a}umliche Probleme mit Methoden der Informatik bewusst und damit erfolgreich zu l{\"o}sen. Wir halten es f{\"u}r besonders wichtig, dass man neue Probleme sorgf{\"a}ltig mathematisch modelliert und mittels exakter Algorithmen das eigene Modell wenigstens auf kleinen Instanzen {\"u}berpr{\"u}ft, bevor man sich schnellen Heuristiken zuwendet, um groSSe Instanzen zu l{\"o}sen.}, author = {Haunert, J.-H. and Wolff, A.}, booktitle = {Handbuch der Geodäsie: 5 Bände}, doi = {10.1007/978-3-662-46900-2_69-1}, editor = {Freeden, W. and Rummel, R.}, isbn = {978-3-662-46900-2}, pages = {1--39}, publisher = {Springer Berlin Heidelberg}, title = {Räumliche Analyse durch kombinatorische Optimierung}, url = {https://doi.org/10.1007/978-3-662-46900-2_69-1}, year = {2016} }
	J.-H. Haunert, and W. Meulemans. Partitioning polygons via graph augmentation. In volume 9927 of Lecture Notes in Computer Science. Proc. 9th International Conference on Geographic Information Science (GIScience 2016), pages 18-33. Springer-Verlag, 2016. doi bibtex
	doi:10.1007/978-3-319-45738-3_2 @inproceedings{HaunertMeulemans2016, author = {Haunert, J.-H. and Meulemans, W.}, booktitle = {Proc. 9th International Conference on Geographic Information Science (GIScience 2016)}, doi = {10.1007/978-3-319-45738-3\_2}, pages = {18{--}33}, publisher = {Springer-Verlag}, series = {Lecture Notes in Computer Science}, title = {Partitioning Polygons via Graph Augmentation}, url = {https://doi.org/10.1007/978-3-319-45738-3\_2}, volume = {9927}, year = {2016} }
	D. Peng, A. Wolff, and J.-H. Haunert. Continuous generalization of administrative boundaries based on compatible triangulations. In Lecture Notes in Geoinformation and Cartography. Proc. 19th AGILE International Conference on Geographic Information Science, pages 399-415. Springer-Verlag, 2016. doi bibtex
	doi:10.1007/978-3-319-33783-8_23 @inproceedings{PengEtAl2016, author = {Peng, D. and Wolff, A. and Haunert, J.-H.}, booktitle = {Proc. 19th AGILE International Conference on Geographic Information Science}, doi = {10.1007/978-3-319-33783-8_23}, pages = {399{--}415}, publisher = {Springer-Verlag}, series = {Lecture Notes in Geoinformation and Cartography}, title = {Continuous Generalization of Administrative Boundaries Based on Compatible Triangulations}, year = {2016} }
	J.-H Haunert, and A Wolff. Beyond maximum independent set: an extended model for point-feature label placement. In volume XLI-B2 of International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences. Proc. XXIII ISPRS Congress, pages 109-114. 2016. bibtex
	@inproceedings{haunertwolff2016, author = {Haunert, J.-H and Wolff, A}, booktitle = {Proc. XXIII ISPRS Congress}, pages = {109{--}114}, series = {International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences}, title = {Beyond Maximum Independent Set: An Extended Model for Point-Feature Label Placement}, volume = {XLI-B2}, year = {2016} }

	A. Gemsa, J.-H. Haunert, and M. Nöllenburg. Multirow boundary-labeling algorithms for panorama images. ACM Transations on Spatial Algorithms and Systems, 1(1):1-30, 2015. abstract doi bibtex
	Boundary labeling deals with placing annotations for objects in an image on the boundary of that image. This problem occurs frequently in situations in which placing labels directly in the image is impossible or produces too much visual clutter. Examples are annotating maps, photos, or technical/medical illustrations. Previous algorithmic results for boundary labeling consider a single layer of labels along some or all sides of a rectangular image. If, however, the number of labels is large or the labels are too long, multiple layers of labels are needed. In this article, we study boundary labeling for panorama images, where n points in a rectangle R are to be annotated by disjoint unit-height rectangular labels placed above R in K different rows (or layers). Each point is connected to its label by a vertical leader that does not intersect any other label. We present polynomial time algorithms based on dynamic programming that either minimize the number of rows to place all n labels or maximize the number (or total weight) of labels that can be placed in K rows for a given integer K. For weighted labels, the problem is shown to be (weakly) NP-hard; in this case, we give a pseudo-polynomial algorithm to maximize the weight of the selected labels. We have implemented our algorithms; the experimental results show that solutions for realistically sized instances are computed instantaneously. We have also investigated two-sided panorama labeling, for which the labels may be placed above or below the panorama image. In this model, all of the aforementioned problems are NP-hard. For solving them, we propose mixed-integer linear program formulations. doi:10.1145/2794299 @article{GemsaHN15, abstract = {Boundary labeling deals with placing annotations for objects in an image on the boundary of that image. This problem occurs frequently in situations in which placing labels directly in the image is impossible or produces too much visual clutter. Examples are annotating maps, photos, or technical/medical illustrations. Previous algorithmic results for boundary labeling consider a single layer of labels along some or all sides of a rectangular image. If, however, the number of labels is large or the labels are too long, multiple layers of labels are needed. In this article, we study boundary labeling for panorama images, where n points in a rectangle R are to be annotated by disjoint unit-height rectangular labels placed above R in K different rows (or layers). Each point is connected to its label by a vertical leader that does not intersect any other label. We present polynomial time algorithms based on dynamic programming that either minimize the number of rows to place all n labels or maximize the number (or total weight) of labels that can be placed in K rows for a given integer K. For weighted labels, the problem is shown to be (weakly) NP-hard; in this case, we give a pseudo-polynomial algorithm to maximize the weight of the selected labels. We have implemented our algorithms; the experimental results show that solutions for realistically sized instances are computed instantaneously. We have also investigated two-sided panorama labeling, for which the labels may be placed above or below the panorama image. In this model, all of the aforementioned problems are NP-hard. For solving them, we propose mixed-integer linear program formulations.}, author = {Gemsa, A. and Haunert, J.{-}H. and N{\"{o}}llenburg, M.}, doi = {10.1145/2794299}, journal = {ACM Transations on Spatial Algorithms and Systems}, number = {1}, pages = {1{--}30}, title = {Multirow Boundary-Labeling Algorithms for Panorama Images}, url = {https://doi.org/10.1145/2794299}, volume = {1}, year = {2015} }
	J.-H. Haunert, and B. Niedermann. An algorithmic framework for labeling network maps. In Proc. 21st International Conference on Computing and Combinatorics (COCOON), pages 689-700. 2015. abstract doi bibtex
	Drawing network maps automatically comprises two challenging steps, namely laying out the map and placing non-overlapping labels. In this paper we tackle the problem of labeling an already existing network map considering the application of metro maps. We present a flexible and versatile labeling model. Despite its simplicity, we prove that it is NP-complete to label a single line of the network. For a restricted variant of that model, we introduce an efficient algorithm that optimally labels a single line. Based on that algorithm, we present a general and sophisticated workflow for multiple metro lines, which is experimentally evaluated on real-world metro maps. doi:10.1007/978-3-319-21398-9_54 @inproceedings{HaunertN15, abstract = {Drawing network maps automatically comprises two challenging steps, namely laying out the map and placing non-overlapping labels. In this paper we tackle the problem of labeling an already existing network map considering the application of metro maps. We present a flexible and versatile labeling model. Despite its simplicity, we prove that it is NP-complete to label a single line of the network. For a restricted variant of that model, we introduce an efficient algorithm that optimally labels a single line. Based on that algorithm, we present a general and sophisticated workflow for multiple metro lines, which is experimentally evaluated on real-world metro maps.}, author = {Haunert, J.{-}H. and Niedermann, B.}, booktitle = {Proc. 21st International Conference on Computing and Combinatorics (COCOON)}, doi = {10.1007/978-3-319-21398-9\_54}, pages = {689{--}700}, title = {An Algorithmic Framework for Labeling Network Maps}, url = {https://doi.org/10.1007/978-3-319-21398-9\_54}, year = {2015} }
	N. Schwartges, B. Morgan, J.-H. Haunert, and A. Wolff. Labeling streets along a route in interactive 3d maps using billboards. In Proc. 18th AGILE International Conference on Geographic Information Science, pages 269-287. 2015. doi bibtex
	doi:10.1007/978-3-319-16787-9_16 @inproceedings{SchwartgesEtAl2015, author = {Schwartges, N. and Morgan, B. and Haunert, J.-H. and Wolff, A.}, booktitle = {Proc. 18th AGILE International Conference on Geographic Information Science}, doi = {10.1007/978-3-319-16787-9\_16}, pages = {269{--}287}, title = {Labeling Streets Along a Route in Interactive 3D Maps Using Billboards}, url = {https://doi.org/10.1007/978-3-319-16787-9\_16}, year = {2015} }
	J. Sultan, G. Ben-Haim, J.-H. Haunert, and S. Dalyot. User-generated data for analyzing road-type use of cyclists. In Proc. Joint Workshop of FIG Commission 3 & Commission 7 on Crowdsourcing of Land Information. 2015. FIG Article of the Month - December 2015 bibtex
	@inproceedings{label5321, author = {Sultan, J. and Ben-Haim, G. and Haunert, J.-H. and Dalyot, S.}, booktitle = {Proc. Joint Workshop of FIG Commission 3 \& Commission 7 on Crowdsourcing of Land Information}, note = {FIG Article of the Month {--} December 2015}, title = {User-Generated Data for Analyzing Road-Type Use of Cyclists}, url = {http://www.fig.net/resources/monthly\_articles/2015/Sultan\_etal\_december\_2015.asp}, year = {2015} }

	M. Sester, J. Jokar~Arsanjani, R. Klammer, D. Burghardt, and J.-H. Haunert. Integrating and generalising volunteered geographic information. In D. Burghardt, C. Duchene, and W. Mackaness, editors, Lecture Notes in Geoinformation and Cartography. Abstracting Geographic Information in a Data Rich World. Springer-Verlag, Berlin, Germany, 2014. abstract doi bibtex
	The availability of spatial data on the web has greatly increased through the availability of user-generated community data and geosensor networks. The integration of such multi-source data is providing promising opportunities, as integrated information is richer than can be found in only one data source, but also poses new challenges due to the heterogeneity of the data, the differences in quality and in respect of tag-based semantic modelling. The chapter describes approaches for the integration of official and informal sources, and discusses the impact of integrating user-generated data on automated generalisation and visualisation. doi:10.1007/978-3-319-00203-3_5 @inproceedings{SesterEtAl2014, abstract = {The availability of spatial data on the web has greatly increased through the availability of user-generated community data and geosensor networks. The integration of such multi-source data is providing promising opportunities, as integrated information is richer than can be found in only one data source, but also poses new challenges due to the heterogeneity of the data, the differences in quality and in respect of tag-based semantic modelling. The chapter describes approaches for the integration of official and informal sources, and discusses the impact of integrating user-generated data on automated generalisation and visualisation.}, author = {M. Sester and J. {Jokar~Arsanjani} and R. Klammer and D. Burghardt and J.-H. Haunert}, booktitle = {Abstracting Geographic Information in a Data Rich World}, doi = {10.1007/978-3-319-00203-3_5}, editor = {Burghardt, D. and Duchene, C. and Mackaness, W.}, publisher = {Springer-Verlag, Berlin, Germany}, series = {Lecture Notes in Geoinformation and Cartography}, title = {Integrating and Generalising Volunteered Geographic Information}, year = {2014} }
	T. C. van Dijk, and J.-H. Haunert. Interactive focus maps using least-squares optimization. International Journal of Geographical Information Science, 28(10), 2014. abstract doi bibtex
	We present a new algorithm that enlarges a focus region in a given network map without removing non-focus (i.e., context) network parts from the map or changing the map's size. In cartography, this problem is usually tackled with fish-eye projections, which, however, introduce severe distortion. Our new algorithm minimizes distortion and, with respect to this objective, produces results of similar quality compared to an existing algorithm. In contrast to the existing algorithm, the new algorithm achieves real-time performance that allows its application in interactive systems. We target applications where a user sets a focus by brushing parts of the network or the focus region is defined as the neighborhood of a moving user. A crucial feature of the algorithm is its capability of avoiding unwanted edge crossings. Basically, we first solve a least-squares optimization problem without constraints for avoiding edge crossings. The solution we find is then used to identify a small set of constraints needed for a crossing-free solution and, beyond this, allows us to start an animation enlarging the focus region before the final, crossing-free solution is found. Moreover, memorizing the non-crossing constraints from an initial run of the algorithm allows us to achieve a better runtime on any further run - assuming that the focus region does not move too much between two consecutive runs. As we show with experiments on real-world data, this enables response times well below 1 second. doi:10.1080/13658816.2014.887718 @article{VanDijkHaunert, abstract = {We present a new algorithm that enlarges a focus region in a given network map without removing non-focus (i.e., context) network parts from the map or changing the map's size. In cartography, this problem is usually tackled with fish-eye projections, which, however, introduce severe distortion. Our new algorithm minimizes distortion and, with respect to this objective, produces results of similar quality compared to an existing algorithm. In contrast to the existing algorithm, the new algorithm achieves real-time performance that allows its application in interactive systems. We target applications where a user sets a focus by brushing parts of the network or the focus region is defined as the neighborhood of a moving user. A crucial feature of the algorithm is its capability of avoiding unwanted edge crossings. Basically, we first solve a least-squares optimization problem without constraints for avoiding edge crossings. The solution we find is then used to identify a small set of constraints needed for a crossing-free solution and, beyond this, allows us to start an animation enlarging the focus region before the final, crossing-free solution is found. Moreover, memorizing the non-crossing constraints from an initial run of the algorithm allows us to achieve a better runtime on any further run - assuming that the focus region does not move too much between two consecutive runs. As we show with experiments on real-world data, this enables response times well below 1 second.}, author = {T. C. van Dijk and J.-H. Haunert}, doi = {10.1080/13658816.2014.887718}, journal = {International Journal of Geographical Information Science}, number = {10}, title = {Interactive Focus Maps Using Least-Squares Optimization}, volume = {28}, year = {2014} }
	T. C. van Dijk, A. van Goethem, J.-H. Haunert, W. Meulemans, and B. Speckmann. An automated method for circular-arc metro maps. In Abstracts of the Schematic Mapping Workshop 2014. 2014. bibtex
	@inproceedings{vanDijkEtAl2014, author = {T. C. van Dijk and A. van Goethem and J.-H. Haunert and W. Meulemans and B. Speckmann}, booktitle = {Abstracts of the Schematic Mapping Workshop 2014}, title = {An Automated Method for Circular-Arc Metro Maps}, url = {https://sites.google.com/site/schematicmapping/Dijk-Circular.pdf}, year = {2014} }
	M. Chimani, T. C. van Dijk, and J.-H. Haunert. How to eat a graph: computing selection sequences for the continuous generalization of road networks. In Proc. 22nd ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM SIGSPATIAL GIS '14), pages 243-252. 2014. doi bibtex
	doi:10.1145/2666310.2666414 @inproceedings{ChimaniEtAl2014, author = {M. Chimani and T. C. van Dijk and J.-H. Haunert}, booktitle = {Proc. 22nd ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM SIGSPATIAL GIS '14)}, doi = {10.1145/2666310.2666414}, pages = {243--252}, title = {How to Eat a Graph: Computing Selection Sequences for the Continuous Generalization of Road Networks}, year = {2014} }
	T. C. van Dijk, A. van Goethem, J.-H. Haunert, W. Meulemans, and B. Speckmann. Map schematization with circular arcs. In volume 8728 of Lecture Notes in Computer Science. Proc. 8th International Conference on Geographic Information Science (GIScience'14), pages 1-17. Springer-Verlag, Berlin, Germany, 2014. doi bibtex
	doi:10.1007/978-3-319-11593-1_1 @inproceedings{DijkEtAl2014, author = {T. C. van Dijk and A. van Goethem and J.-H. Haunert and W. Meulemans and B. Speckmann}, booktitle = {Proc. 8th International Conference on Geographic Information Science (GIScience'14)}, doi = {10.1007/978-3-319-11593-1_1}, pages = {1--17}, publisher = {Springer-Verlag, Berlin, Germany}, series = {Lecture Notes in Computer Science}, title = {Map Schematization with Circular Arcs}, volume = {8728}, year = {2014} }
	J.-H. Haunert, and T. Hermes. Labeling circular focus regions based on a tractable case of maximum weight independent set of rectangles. In Proc. 2nd ACM SIGSPATIAL Workshop on MapInteraction. 2014. doi bibtex
	doi:10.1145/2677068.2677069 @inproceedings{HaunertHermes2014, author = {J.-H. Haunert and T. Hermes}, booktitle = {Proc. 2nd ACM SIGSPATIAL Workshop on MapInteraction}, doi = {10.1145/2677068.2677069}, numpages = {7}, title = {Labeling Circular Focus Regions Based on a Tractable Case of Maximum Weight Independent Set of Rectangles}, year = {2014} }
	N. Schwartges, J.-H. Haunert, D. Zwiebler, and A. Wolff. Point labeling with sliding labels in interactive maps. In Lecture Notes in Geoinformation and Cartography. Proc. 17th AGILE International Conference on Geographic Information Science, pages 295-310. Springer-Verlag, Berlin, Germany, 2014. doi bibtex
	doi:10.1007/978-3-319-03611-3_17 @inproceedings{SchwartgesEtAl2014, author = {N. Schwartges and J.-H. Haunert and D. Zwiebler and A. Wolff}, booktitle = {Proc. 17th AGILE International Conference on Geographic Information Science}, doi = {10.1007/978-3-319-03611-3_17}, pages = {295--310}, publisher = {Springer-Verlag, Berlin, Germany}, series = {Lecture Notes in Geoinformation and Cartography}, title = {Point Labeling with Sliding Labels in Interactive Maps}, year = {2014} }
	N. Schwartges, A. Wolff, and J.-H. Haunert. Labeling streets in interactive maps using embedded labels. In Proc. 22nd ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM SIGSPATIAL GIS '14), pages 517-520. 2014. doi bibtex
	doi:10.1145/2666310.2666494 @inproceedings{SchwartgesEtAl2014b, author = {N. Schwartges and A. Wolff and J.-H. Haunert}, booktitle = {Proc. 22nd ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM SIGSPATIAL GIS '14)}, doi = {10.1145/2666310.2666494}, pages = {517--520}, title = {Labeling Streets in Interactive Maps Using Embedded Labels}, year = {2014} }

	M. Fink, J.-H. Haunert, J. Spoerhase, and A. Wolff. Selecting the aspect ratio of a scatter plot based on its Delaunay triangulation. In Proc. 29th European Workshop on Computational Geometry (EuroCG'13). 2013. abstract bibtex
	Scatter plots are diagrams that visualize sets of points in two dimensions. They allow users to detect correlations and clusters in the data. Whether a user can accomplish these tasks highly depends on the aspect ratio selected for the plot, i.e., the ratio between the horizontal and the vertical extent of the diagram. We argue that an aspect ratio is good if the Delaunay triangulation of the scatter plot has some nice geometric property, e.g., a large minimum angle or a small total edge length. In order to find an optimum aspect ratio according to a given criterion we present an algorithm that efficiently maintains the Delaunay triangulation of the point set when traversing all aspect ratios @inproceedings{FinkEtAl2013, abstract = {Scatter plots are diagrams that visualize sets of points in two dimensions. They allow users to detect correlations and clusters in the data. Whether a user can accomplish these tasks highly depends on the aspect ratio selected for the plot, i.e., the ratio between the horizontal and the vertical extent of the diagram. We argue that an aspect ratio is good if the Delaunay triangulation of the scatter plot has some nice geometric property, e.g., a large minimum angle or a small total edge length. In order to find an optimum aspect ratio according to a given criterion we present an algorithm that efficiently maintains the Delaunay triangulation of the point set when traversing all aspect ratios}, author = {Fink, M. and Haunert, J.-H. and Spoerhase, J. and Wolff, A.}, booktitle = {Proc. 29th European Workshop on Computational Geometry (EuroCG'13)}, timestamp = {2013-01-29T14:57:50.000+0100}, title = {Selecting the Aspect Ratio of a Scatter Plot Based on Its {D}elaunay Triangulation}, year = {2013} }
	M. Fink, J.-H. Haunert, J. Spoerhase, and A. Wolff. Selecting the aspect ratio of a scatter plot based on its Delaunay triangulation. IEEE Transactions on Visualization and Computer Graphics), 19(12):2326-2335, 2013. abstract doi bibtex
	Scatter plots are diagrams that visualize two-dimensional data as sets of points in the plane. They allow users to detect correlations and clusters in the data. Whether or not a user can accomplish these tasks highly depends on the aspect ratio selected for the plot, i.e., the ratio between the horizontal and the vertical extent of the diagram. We argue that an aspect ratio is good if the Delaunay triangulation of the scatter plot at this aspect ratio has some nice geometric property, e.g., a large minimum angle or a small total edge length. More precisely, we consider the following optimization problem. Given a set Q of points in the plane, find a scale factor s such that scaling the x-coordinates of the points in Q by s and the y-coordinates by 1=s yields a point set P(s) that optimizes a property of the Delaunay triangulation of P(s), over all choices of s. We present an algorithm that solves this problem efficiently and demonstrate its usefulness on real-world instances. Moreover, we discuss an empirical test in which we asked 64 participants to choose the aspect ratios of 18 scatter plots. We tested six different quality measures that our algorithm can optimize. In conclusion, minimizing the total edge length and minimizing what we call the 'uncompactness' of the triangles of the Delaunay triangulation yielded the aspect ratios that were most similar to those chosen by the participants in the test. doi:10.1109/TVCG.2013.187 @article{FinkEtAl2013b, abstract = {Scatter plots are diagrams that visualize two-dimensional data as sets of points in the plane. They allow users to detect correlations and clusters in the data. Whether or not a user can accomplish these tasks highly depends on the aspect ratio selected for the plot, i.e., the ratio between the horizontal and the vertical extent of the diagram. We argue that an aspect ratio is good if the Delaunay triangulation of the scatter plot at this aspect ratio has some nice geometric property, e.g., a large minimum angle or a small total edge length. More precisely, we consider the following optimization problem. Given a set Q of points in the plane, find a scale factor s such that scaling the x-coordinates of the points in Q by s and the y-coordinates by 1=s yields a point set P(s) that optimizes a property of the Delaunay triangulation of P(s), over all choices of s. We present an algorithm that solves this problem efficiently and demonstrate its usefulness on real-world instances. Moreover, we discuss an empirical test in which we asked 64 participants to choose the aspect ratios of 18 scatter plots. We tested six different quality measures that our algorithm can optimize. In conclusion, minimizing the total edge length and minimizing what we call the 'uncompactness' of the triangles of the Delaunay triangulation yielded the aspect ratios that were most similar to those chosen by the participants in the test.}, author = {Fink, M. and Haunert, J.-H. and Spoerhase, J. and Wolff, A.}, doi = {10.1109/TVCG.2013.187}, journal = {IEEE Transactions on Visualization and Computer Graphics)}, number = {12}, pages = {2326--2335}, timestamp = {2013-07-25T18:19:08.000+0200}, title = {Selecting the Aspect Ratio of a Scatter Plot Based on Its {D}elaunay Triangulation}, volume = {19}, year = {2013} }
	J.-H. Haunert. An algorithmic approach to geographic information science. Universität Würzburg. Fakultät für Mathematik und Informatik, 2013. Habilitationsschrift (kumulativ). bibtex
	@phdthesis{Haunert2013b, author = {Haunert, J.-H.}, file = {Haunert_Habil.pdf:http\://www1.pub.informatik.uni-wuerzburg.de/pub/haunert/pdf/Haunert_Habil.pdf:PDF}, school = {Fakult\"{a}t f\"{u}r Mathematik und Informatik}, series = {Universit\"{a}t W\"{u}rzburg}, timestamp = {2013-07-25T14:07:36.000+0200}, title = {An Algorithmic Approach to Geographic Information Science}, type = {Habilitationsschrift (kumulativ)}, year = {2013} }
	D. Peng, J.-H. Haunert, A. Wolff, and C. Hurter. Morphing polylines based on least-squares adjustment. In Proc. 16th ICA Generalisation Workshop. 2013. bibtex
	@inproceedings{Peng2013, author = {Peng, D. and Haunert, J.-H. and Wolff, A. and Hurter, C.}, booktitle = {Proc. 16th ICA Generalisation Workshop}, timestamp = {2013-05-13T17:21:59.000+0200}, title = {Morphing Polylines Based on Least-Squares Adjustment}, year = {2013} }
	Nadine Schwartges, Dennis Allerkamp, J.-H. Haunert, and A. Wolff. Optimizing active ranges for point selection in dynamic maps. In Proc. 16th ICA Generalisation Workshop. 2013. bibtex
	@inproceedings{Schwartges2013, author = {Schwartges, Nadine and Allerkamp, Dennis and Haunert, J.-H. and Wolff, A.}, booktitle = {Proc. 16th ICA Generalisation Workshop}, timestamp = {2013-05-13T17:07:20.000+0200}, title = {Optimizing Active Ranges for Point Selection in Dynamic Maps}, year = {2013} }
	T. C. van Dijk, A. van Goethem, J.-H. Haunert, W. Meulemans, and B. Speckmann. Accentuating focus maps via partial schematization. In Proc. 21st ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM SIGSPATIAL GIS '13), pages 418-421. 2013. abstract doi bibtex
	We present an algorithm for schematized focus maps. Focus maps integrate a high detailed, enlarged focus region continuously in a given base map. Recent methods integrate both with such low distortion that the focus region becomes hard to identify. We combine focus maps with partial schematization to display distortion of the context and to emphasize the focus region. Schematization visually conveys geographical accuracy, while not increasing map complexity. We extend the focus-map algorithm to incorporate geometric proximity relationships and show how to combine focus maps with schematization in order to cater to different use cases. doi:10.1145/2525314.2525452 @inproceedings{vanDijkEtAl2013, abstract = {We present an algorithm for schematized focus maps. Focus maps integrate a high detailed, enlarged focus region continuously in a given base map. Recent methods integrate both with such low distortion that the focus region becomes hard to identify. We combine focus maps with partial schematization to display distortion of the context and to emphasize the focus region. Schematization visually conveys geographical accuracy, while not increasing map complexity. We extend the focus-map algorithm to incorporate geometric proximity relationships and show how to combine focus maps with schematization in order to cater to different use cases.}, author = {T. C. van Dijk and A. van Goethem and J.-H. Haunert and W. Meulemans and B. Speckmann}, booktitle = {Proc. 21st ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM SIGSPATIAL GIS '13)}, doi = {10.1145/2525314.2525452}, pages = {418--421}, title = {Accentuating focus maps via partial schematization}, year = {2013} }
	T. C. van Dijk, and J.-H. Haunert. A probabilistic model for road selection in mobile maps. In Proc. 12th International Symposium on Web and Wireless Geographical Information Systems (W2GIS'13), pages 214-222. 2013. abstract doi bibtex
	Mobile devices provide an interesting context for map drawing. This paper presents a novel road-selection algorithm based on PageRank, the algorithm famously used by Google to rank web pages by importance. Underlying the PageRank calculation is a probabilistic model of user behavior. We provide suitable generalizations of this model to road networks. Our implementation of the proposed algorithm handles a sizable map in approximately a tenth of a second on a desktop PC. Therefore, our methods should be feasible on modern mobile devices. doi:10.1007/978-3-642-37087-8_16 @inproceedings{VanDijkHaunert2013, abstract = {Mobile devices provide an interesting context for map drawing. This paper presents a novel road-selection algorithm based on PageRank, the algorithm famously used by Google to rank web pages by importance. Underlying the PageRank calculation is a probabilistic model of user behavior. We provide suitable generalizations of this model to road networks. Our implementation of the proposed algorithm handles a sizable map in approximately a tenth of a second on a desktop PC. Therefore, our methods should be feasible on modern mobile devices.}, author = {van Dijk, T. C. and Haunert, J.-H.}, booktitle = {Proc. 12th International Symposium on Web and Wireless Geographical Information Systems (W2GIS'13)}, doi = {10.1007/978-3-642-37087-8_16}, pages = {214--222}, timestamp = {2013-01-29T14:57:51.000+0100}, title = {A probabilistic model for road selection in mobile maps}, year = {2013} }
	T. C. van Dijk, K. Fleszar, J.-H. Haunert, and J. Spoerhase. Road segment selection with strokes and stability. In Proc. 1st ACM SIGSPATIAL Workshop on MapInteraction. 2013. abstract doi bibtex
	In order to visualize a road network without producing visual clutter, a subset of all road segments needs to be selected. Many algorithms for road segment selection are based on a relevance score for edges in a network (for example betweenness centrality) and proceed by taking a greedy selection based on these weights. This can give dissatisfactory results. In order to improve readability, we introduce a stroke-based constraint and provide an efficient dynamic program that makes an optimal selection given this constraint. Next, we consider the computation of animated road selections from changing edge weights (for example a focus area that follows a moving user). Handling each time step of the animation individually can lead to distracting flickering effects. Here we introduce an optimization objective to achieve a more stable selection and provide a polynomial-time algorithm for solving it. While separately solvable in polynomial time, we show that the combination of the stroke constraints and stability optimization is NP-hard. doi:10.1145/2534931.2534936 @inproceedings{vanDijkHaunert2013b, abstract = {In order to visualize a road network without producing visual clutter, a subset of all road segments needs to be selected. Many algorithms for road segment selection are based on a relevance score for edges in a network (for example betweenness centrality) and proceed by taking a greedy selection based on these weights. This can give dissatisfactory results. In order to improve readability, we introduce a stroke-based constraint and provide an efficient dynamic program that makes an optimal selection given this constraint. Next, we consider the computation of animated road selections from changing edge weights (for example a focus area that follows a moving user). Handling each time step of the animation individually can lead to distracting flickering effects. Here we introduce an optimization objective to achieve a more stable selection and provide a polynomial-time algorithm for solving it. While separately solvable in polynomial time, we show that the combination of the stroke constraints and stability optimization is NP-hard.}, author = {van Dijk, T. C. and Fleszar, K. and Haunert, J.-H. and Spoerhase, J.}, booktitle = {Proc. 1st ACM SIGSPATIAL Workshop on MapInteraction}, doi = {10.1145/2534931.2534936}, journal = {Unknown Journal}, title = {Road segment selection with strokes and stability}, year = {2013} }

	M. Fink, J.-H. Haunert, T. Mchedlidze, J. Spoerhase, and A. Wolff. Drawing graphs with vertices at specified positions and crossings at large angles. In volume 7157 of Lecture Notes in Computer Science. Proc. Workshop on Algorithms and Computation (WALCOM'12), pages 186-197. Springer-Verlag, Berlin, Germany, 2012. abstract doi bibtex
	In point-set-embeddability (PSE) problems one is given not just a graph that is to be drawn, but also a set of points in the plane that specify where the vertices of the graph can be placed. The problem class was introduced by Gritzmann et al. [3] twenty years ago. In their work and most other works on PSE problems, however, planarity of the output drawing was an essential requirement. Recent experiments on the readability of drawings [4] showed that polyline drawings with angles at edge crossings close to 90 degrees. and a small number of bends per edge are just as readable as planar drawings. Motivated by these findings, Didimo et al. [2] recently introduced RAC drawings where pairs of crossing edges must form a right angle and, more generally, xAC drawings (for x in (0, 90]) where the crossing angle must be at least x. As usual, edges may not overlap and may not go through vertices. We investigate the intersection of PSE and RAC/xAC. doi:10.1007/978-3-642-25878-7_43 @inproceedings{Fink2012, abstract = {In point-set-embeddability (PSE) problems one is given not just a graph that is to be drawn, but also a set of points in the plane that specify where the vertices of the graph can be placed. The problem class was introduced by Gritzmann et al. [3] twenty years ago. In their work and most other works on PSE problems, however, planarity of the output drawing was an essential requirement. Recent experiments on the readability of drawings [4] showed that polyline drawings with angles at edge crossings close to 90 degrees. and a small number of bends per edge are just as readable as planar drawings. Motivated by these findings, Didimo et al. [2] recently introduced RAC drawings where pairs of crossing edges must form a right angle and, more generally, xAC drawings (for x in (0, 90]) where the crossing angle must be at least x. As usual, edges may not overlap and may not go through vertices. We investigate the intersection of PSE and RAC/xAC.}, author = {Fink, M. and Haunert, J.-H. and Mchedlidze, T. and Spoerhase, J. and Wolff, A.}, booktitle = {Proc. Workshop on Algorithms and Computation (WALCOM'12)}, doi = {10.1007/978-3-642-25878-7_43}, pages = {186--197}, publisher = {Springer-Verlag, Berlin, Germany}, series = {Lecture Notes in Computer Science}, timestamp = {2011-12-16T11:22:02.000+0100}, title = {Drawing Graphs with Vertices at Specified Positions and Crossings at Large Angles}, url = {http://www1.informatik.uni-wuerzburg.de/pub/wolff/pub/fhmsw-dgvsp-12.pdf}, volume = {7157}, year = {2012} }
	M. Fink, J.-H. Haunert, A. Schulz, J. Spoerhase, and A. Wolff. Algorithms for labeling focus regions. IEEE Transactions on Visualization and Computer Graphics, 18(12):2583-2592, 2012. abstract doi bibtex
	In this paper, we investigate the problem of labeling point sites in focus regions of maps or diagrams. This problem occurs, for example, when the user of a mapping service wants to see the names of restaurants or other POIs in a crowded downtown area but keep the overview over a larger area. Our approach is to place the labels at the boundary of the focus region and connect each site with its label by a linear connection, which is called a leader. In this way, we move labels from the focus region to the less valuable context region surrounding it. In order to make the leader layout well readable, we present algorithms that rule out crossings between leaders and optimize other characteristics such as total leader length and distance between labels. \par This yields a new variant of the boundary labeling problem, which has been studied in the literature. Other than in traditional boundary labeling, where leaders are usually schematized polylines, we focus on leaders that are either straight-line segments or Bézier curves. Further, we present algorithms that, given the sites, find a position of the focus region that optimizes the above characteristics. \par We also consider a variant of the problem where we have more sites than space for labels. In this situation, we assume that the sites are prioritized by the user. Alternatively, we take a new facility-location perspective which yields a clustering of the sites. We label one representative of each cluster. If the user wishes, we apply our approach to the sites within a cluster, giving details on demand. doi:10.1109/TVCG.2012.193 @article{FinkEtAl2012, abstract = {In this paper, we investigate the problem of labeling point sites in focus regions of maps or diagrams. This problem occurs, for example, when the user of a mapping service wants to see the names of restaurants or other POIs in a crowded downtown area but keep the overview over a larger area. Our approach is to place the labels at the boundary of the focus region and connect each site with its label by a linear connection, which is called a leader. In this way, we move labels from the focus region to the less valuable context region surrounding it. In order to make the leader layout well readable, we present algorithms that rule out crossings between leaders and optimize other characteristics such as total leader length and distance between labels. \par This yields a new variant of the boundary labeling problem, which has been studied in the literature. Other than in traditional boundary labeling, where leaders are usually schematized polylines, we focus on leaders that are either straight-line segments or B\'ezier curves. Further, we present algorithms that, given the sites, find a position of the focus region that optimizes the above characteristics. \par We also consider a variant of the problem where we have more sites than space for labels. In this situation, we assume that the sites are prioritized by the user. Alternatively, we take a new facility-location perspective which yields a clustering of the sites. We label one representative of each cluster. If the user wishes, we apply our approach to the sites within a cluster, giving details on demand.}, author = {Fink, M. and Haunert, J.-H. and Schulz, A. and Spoerhase, J. and Wolff, A.}, doi = {10.1109/TVCG.2012.193}, file = {fhssw-alfr-InfoVis12.pdf:http\://www1.informatik.uni-wuerzburg.de/pub/fink/paper/fhssw-alfr-InfoVis12.pdf:PDF}, journal = {IEEE Transactions on Visualization and Computer Graphics}, number = {12}, pages = {2583--2592}, timestamp = {2013-03-13T10:23:34.000+0100}, title = {Algorithms for Labeling Focus Regions}, volume = {18}, year = {2012} }
	J.-H. Haunert. A symmetry detector for map generalization and urban-space analysis. ISPRS Journal of Photogrammetry and Remote Sensing, 74:66-77, 2012. abstract doi bibtex
	This article presents an algorithmic approach to the problem of finding symmetries in building footprints, which is motivated by map generalization tasks such as symmetry-preserving building simplification and symmetry-aware grouping and aggregation. Moreover, symmetries in building footprints may be used for landmark selection and building classification. The presented method builds up on existing methods for symmetry detection in vector data that use algorithms for string matching. It detects both mirror symmetries and repetitions of geometric structures. In addition to the existing vector-based methods, the new method finds partial symmetries in polygons while allowing for small geometric errors and, based on a least-squares approach, computes optimally adjusted mirror axes and assesses their quality. Finally, the problem of grouping symmetry relations is addressed with an algorithm that finds mirror axes that are almost collinear. The presented approach was tested on a large building dataset of the metropolitan Boston area and its results were compared with results that were manually generated in an empirical test. The symmetry relations that the participants of the test considered most important were found by the algorithm. Future work will deal with the integration of information on symmetry relations into algorithms for map generalization. doi:10.1016/j.isprsjprs.2012.08.004 @article{Haunert2012, abstract = {This article presents an algorithmic approach to the problem of finding symmetries in building footprints, which is motivated by map generalization tasks such as symmetry-preserving building simplification and symmetry-aware grouping and aggregation. Moreover, symmetries in building footprints may be used for landmark selection and building classification. The presented method builds up on existing methods for symmetry detection in vector data that use algorithms for string matching. It detects both mirror symmetries and repetitions of geometric structures. In addition to the existing vector-based methods, the new method finds partial symmetries in polygons while allowing for small geometric errors and, based on a least-squares approach, computes optimally adjusted mirror axes and assesses their quality. Finally, the problem of grouping symmetry relations is addressed with an algorithm that finds mirror axes that are almost collinear. The presented approach was tested on a large building dataset of the metropolitan Boston area and its results were compared with results that were manually generated in an empirical test. The symmetry relations that the participants of the test considered most important were found by the algorithm. Future work will deal with the integration of information on symmetry relations into algorithms for map generalization.}, author = {Haunert, J.-H.}, doi = {10.1016/j.isprsjprs.2012.08.004}, file = {HaunertISPRS2012.pdf:http\://www1.informatik.uni-wuerzburg.de/pub/haunert/pdf/HaunertISPRS2012.pdf:PDF}, journal = {ISPRS Journal of Photogrammetry and Remote Sensing}, pages = {66--77}, timestamp = {2013-03-13T10:45:41.000+0100}, title = {A Symmetry Detector for Map Generalization and Urban-Space Analysis}, volume = {74}, year = {2012} }
	J.-H. Haunert, and B. Budig. An algorithm for map matching given incomplete road data. In Proc. 20th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM SIGSPATIAL GIS '12), pages 510-513. 2012. abstract bibtex
	We consider the problem of matching a GPS trajectory with a road data set in which some roads are missing. To solve this problem, we extend a map-matching algorithm by Newson and Krumm (Proc. ACM GIS 2009, pp. 336-343) that is based on a hidden Markov model and a discrete set of candidate matches for each point of the trajectory. We introduce an additional off-road candidate for each point of the trajectory. The output path becomes determined by selecting one candidate for each point of the trajectory and connecting the selected candidates via shortest paths, which preferably lie in the road network but, if off-road candidates become selected, may also include off-road sections. We discuss experiments with GPS tracks of pedestrians. @inproceedings{HaunertBudig2012, abstract = {We consider the problem of matching a GPS trajectory with a road data set in which some roads are missing. To solve this problem, we extend a map-matching algorithm by Newson and Krumm (Proc. ACM GIS 2009, pp. 336--343) that is based on a hidden Markov model and a discrete set of candidate matches for each point of the trajectory. We introduce an additional off-road candidate for each point of the trajectory. The output path becomes determined by selecting one candidate for each point of the trajectory and connecting the selected candidates via shortest paths, which preferably lie in the road network but, if off-road candidates become selected, may also include off-road sections. We discuss experiments with GPS tracks of pedestrians.}, author = {Haunert, J.-H. and Budig, B.}, booktitle = {Proc. 20th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM SIGSPATIAL GIS '12)}, file = {HaunertBudig2012.pdf:http\://www1.informatik.uni-wuerzburg.de/pub/haunert/pdf/HaunertBudig2012.pdf:PDF}, pages = {510--513}, timestamp = {2013-03-13T10:45:54.000+0100}, title = {An algorithm for map matching given incomplete road data}, url = {http://dl.acm.org/citation.cfm?doid=2424321.2424402}, year = {2012} }

	A. Gemsa, J.-H. Haunert, and M. Nöllenburg. Boundary-labeling algorithms for panorama images. In Proc. 19th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM SIGSPATIAL GIS '11), pages 289-298. 2011. abstract doi bibtex
	Boundary labeling deals with placing annotations for objects in an image on the boundary of that image. This problem occurs frequently in situations where placing labels directly in the image is impossible or produces too much visual clutter. Previous algorithmic results for boundary labeling consider a single layer of labels along some or all sides of a rectangular image. If, however, the number of labels is large or labels are too long, multiple layers of labels are needed. In this paper we study boundary labeling for panorama images, where n points in a rectangle R are to be annotated by disjoint unit-height rectangular labels placed above R in k different rows (or layers). Each point is connected to its label by a vertical leader that does not intersect any other label. We present polynomial-time algorithms based on dynamic programming that either minimize the number of rows to place all n labels, or maximize the number (or total weight) of labels that can be placed in k rows for a given integer k. For weighted labels, the problem is shown to be (weakly) NP-hard, and we give a pseudo-polynomial algorithm to maximize the weight of the selected labels. We have implemented our algorithms; the experimental results show that solutions for realistically-sized instances are computed instantaneously. doi:10.1145/2093973.2094012 @inproceedings{GemsaEtAl2011, abstract = {Boundary labeling deals with placing annotations for objects in an image on the boundary of that image. This problem occurs frequently in situations where placing labels directly in the image is impossible or produces too much visual clutter. Previous algorithmic results for boundary labeling consider a single layer of labels along some or all sides of a rectangular image. If, however, the number of labels is large or labels are too long, multiple layers of labels are needed. In this paper we study boundary labeling for panorama images, where n points in a rectangle R are to be annotated by disjoint unit-height rectangular labels placed above R in k different rows (or layers). Each point is connected to its label by a vertical leader that does not intersect any other label. We present polynomial-time algorithms based on dynamic programming that either minimize the number of rows to place all n labels, or maximize the number (or total weight) of labels that can be placed in k rows for a given integer k. For weighted labels, the problem is shown to be (weakly) NP-hard, and we give a pseudo-polynomial algorithm to maximize the weight of the selected labels. We have implemented our algorithms; the experimental results show that solutions for realistically-sized instances are computed instantaneously.}, author = {Gemsa, A. and Haunert, J.-H. and N\"{o}llenburg, M.}, booktitle = {Proc. 19th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM SIGSPATIAL GIS '11)}, doi = {10.1145/2093973.2094012}, file = {GemsaEtAl2011.pdf:http\://www1.informatik.uni-wuerzburg.de/pub/haunert/pdf/GemsaEtAl2011.pdf:PDF}, pages = {289--298}, timestamp = {2012-04-12T14:43:51.000+0200}, title = {Boundary-Labeling Algorithms for Panorama Images}, year = {2011} }
	J.-H. Haunert. Detecting symmetries in building footprints by string matching. In S. Geertman, W. Reinhardt, and F. Toppen, editors, Lecture Notes in Geoinformation and Cartography. Advancing Geoinformation Science for a Changing World - Proc. 14th AGILE International Conference on Geographic Information Science, pages 319-336. Springer-Verlag, Berlin, Germany, 2011. abstract doi bibtex
	This paper presents an algorithmic approach to the problem of finding symmetries in building footprints. The problem is motivated by map generalization tasks, for example, symmetry-preserving building simplification and symmetry-aware grouping and aggregation. Moreover, symmetries in building footprints may be used for landmark selection and building classification. The presented method builds up on existing methods for symmetry detection in polygons that use algorithms for string matching. It detects both axial symmetries and repetitions of geometric structures. In addition to the existing string-matching approaches to symmetry detection, we consider the problem of finding partial symmetries in polygons while allowing for small geometric errors. Moreover, we discuss how to find optimally adjusted mirror axes and to assess the quality of a detected mirror axis using a least-squares approach. The presented approach was tested on a large building data set of the metropolitan Boston area. The dominant symmetry relations were found. Future work is needed to aggregate the obtained symmetry relations, for example, by finding sets of mirror axes that are almost collinear. Another open problem is the integration of information on symmetry relations into algorithms for map generalization. doi:10.1007/978-3-642-19789-5_16 @inproceedings{Haunert2011, abstract = {This paper presents an algorithmic approach to the problem of finding symmetries in building footprints. The problem is motivated by map generalization tasks, for example, symmetry-preserving building simplification and symmetry-aware grouping and aggregation. Moreover, symmetries in building footprints may be used for landmark selection and building classification. The presented method builds up on existing methods for symmetry detection in polygons that use algorithms for string matching. It detects both axial symmetries and repetitions of geometric structures. In addition to the existing string-matching approaches to symmetry detection, we consider the problem of finding partial symmetries in polygons while allowing for small geometric errors. Moreover, we discuss how to find optimally adjusted mirror axes and to assess the quality of a detected mirror axis using a least-squares approach. The presented approach was tested on a large building data set of the metropolitan Boston area. The dominant symmetry relations were found. Future work is needed to aggregate the obtained symmetry relations, for example, by finding sets of mirror axes that are almost collinear. Another open problem is the integration of information on symmetry relations into algorithms for map generalization.}, author = {Haunert, J.-H.}, booktitle = {Advancing Geoinformation Science for a Changing World -- Proc. 14th AGILE International Conference on Geographic Information Science}, doi = {10.1007/978-3-642-19789-5_16}, editor = {Geertman, S. and Reinhardt, W. and Toppen, F.}, file = {HaunertAgile2011.pdf:http\://www1.informatik.uni-wuerzburg.de/pub/haunert/pdf/HaunertAgile2011.pdf:PDF}, pages = {319--336}, publisher = {Springer-Verlag, Berlin, Germany}, series = {Lecture Notes in Geoinformation and Cartography}, timestamp = {2011-11-07T12:01:01.000+0100}, title = {Detecting Symmetries in Building Footprints by String Matching}, url = {http://www.springerlink.com/content/u280281846852h08/}, year = {2011} }
	J.-H. Haunert. Map generalisation - quality benchmarks through optimisation. GIM International, 25(1):31-33, 2011. abstract bibtex
	Decades of research on map generalisation have resulted in an abundance of heuristic algorithms, evaluation of the performance of which is vital for choosing the most suitable for a certain application. Proper evaluation methods are, however, missing. The author proposes an approach based on optimisation methods adopted from the field of operations research. @article{Haunert2011b, abstract = {Decades of research on map generalisation have resulted in an abundance of heuristic algorithms, evaluation of the performance of which is vital for choosing the most suitable for a certain application. Proper evaluation methods are, however, missing. The author proposes an approach based on optimisation methods adopted from the field of operations research.}, author = {Haunert, J.-H.}, journal = {GIM International}, number = {1}, pages = {31--33}, timestamp = {2011-11-07T12:01:01.000+0100}, title = {Map Generalisation -- Quality Benchmarks through Optimisation}, url = {http://www.gim-international.com/issues/articles/id1644-Map_Generalisation.html}, volume = {25}, year = {2011} }
	J.-H. Haunert, and L. Sering. Drawing road networks with focus regions. IEEE Transactions on Visualization and Computer Graphics, 17(12):2555-2562, 2011. abstract doi bibtex
	Mobile users of maps typically need detailed information about their surroundings plus some context information about remote places. In order to avoid that the map partly gets too dense, cartographers have designed mapping functions that enlarge a user-defined focus region such functions are sometimes called fish-eye projections. The extra map space occupied by the enlarged focus region is compensated by distorting other parts of the map. We argue that, in a map showing a network of roads relevant to the user, distortion should preferably take place in those areas where the network is sparse. Therefore, we do not apply a predefined mapping function. Instead, we consider the road network as a graph whose edges are the road segments. We compute a new spatial mapping with a graph-based optimization approach, minimizing the square sum of distortions at edges. Our optimization method is based on a convex quadratic program (CQP); CQPs can be solved in polynomial time. Important requirements on the output map are expressed as linear inequalities. In particular, we show how to forbid edge crossings. We have implemented our method in a prototype tool. For instances of different sizes, our method generated output maps that were far less distorted than those generated with a predefined fish-eye projection. Future work is needed to automate the selection of roads relevant to the user. Furthermore, we aim at fast heuristics for application in real-time systems. doi:10.1109/TVCG.2011.191 @article{haunertSering2011, abstract = {Mobile users of maps typically need detailed information about their surroundings plus some context information about remote places. In order to avoid that the map partly gets too dense, cartographers have designed mapping functions that enlarge a user-defined focus region such functions are sometimes called fish-eye projections. The extra map space occupied by the enlarged focus region is compensated by distorting other parts of the map. We argue that, in a map showing a network of roads relevant to the user, distortion should preferably take place in those areas where the network is sparse. Therefore, we do not apply a predefined mapping function. Instead, we consider the road network as a graph whose edges are the road segments. We compute a new spatial mapping with a graph-based optimization approach, minimizing the square sum of distortions at edges. Our optimization method is based on a convex quadratic program (CQP); CQPs can be solved in polynomial time. Important requirements on the output map are expressed as linear inequalities. In particular, we show how to forbid edge crossings. We have implemented our method in a prototype tool. For instances of different sizes, our method generated output maps that were far less distorted than those generated with a predefined fish-eye projection. Future work is needed to automate the selection of roads relevant to the user. Furthermore, we aim at fast heuristics for application in real-time systems.}, author = {Haunert, J.-H. and Sering, L.}, doi = {10.1109/TVCG.2011.191}, file = {HaunertSering2011.pdf:http\://www1.informatik.uni-wuerzburg.de/pub/haunert/pdf/HaunertSering2011.pdf:PDF}, journal = {IEEE Transactions on Visualization and Computer Graphics}, number = {12}, pages = {2555--2562}, timestamp = {2012-04-12T14:42:23.000+0200}, title = {Drawing Road Networks with Focus Regions}, volume = {17}, year = {2011} }

	J.-H. Haunert, and A. Wolff. Optimal and topologically safe simplification of building footprints. In Proc. 18th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM SIGSPATIAL GIS '10), pages 192-201. 2010. abstract doi bibtex
	We present an optimization approach to simplify sets of building footprints represented as polygons. We simplify each polygonal ring by selecting a subsequence of its original edges; the vertices of the simplified ring are defined by intersections of consecutive (and possibly extended) edges in the selected sequence. Our aim is to minimize the number of all output edges subject to a user-defined error tolerance. Since we earlier showed that the problem is NP-hard when requiring non-intersecting simple polygons as output, we cannot hope for an efficient, exact algorithm. Therefore, we present an efficient algorithm for a relaxed problem and an integer program (IP) that allows us to solve the original problem with existing software. Our IP is large, since it has O(m^6) constraints, where m is the number of input edges. In order to keep the running time small, we first consider a subset of only O(m) constraints. The choice of the constraints ensures some basic properties of the solution. Constraints that were neglected are added during optimization whenever they become violated by a new solution encountered. Using this approach we simplified a set of 144 buildings with a total of 2056 edges in 4.1 seconds on a standard desktop PC; the simplified building set contained 762 edges. During optimization, the number of constraints increased by a mere 13 %. We also show how to apply cartographic quality measures in our method and discuss their effects on examples. doi:10.1145/1869790.1869819 @inproceedings{haunertwolff2010, abstract = {We present an optimization approach to simplify sets of building footprints represented as polygons. We simplify each polygonal ring by selecting a subsequence of its original edges; the vertices of the simplified ring are defined by intersections of consecutive (and possibly extended) edges in the selected sequence. Our aim is to minimize the number of all output edges subject to a user-defined error tolerance. Since we earlier showed that the problem is NP-hard when requiring non-intersecting simple polygons as output, we cannot hope for an efficient, exact algorithm. Therefore, we present an efficient algorithm for a relaxed problem and an integer program (IP) that allows us to solve the original problem with existing software. Our IP is large, since it has O(m^6) constraints, where m is the number of input edges. In order to keep the running time small, we first consider a subset of only O(m) constraints. The choice of the constraints ensures some basic properties of the solution. Constraints that were neglected are added during optimization whenever they become violated by a new solution encountered. Using this approach we simplified a set of 144 buildings with a total of 2056 edges in 4.1 seconds on a standard desktop PC; the simplified building set contained 762 edges. During optimization, the number of constraints increased by a mere 13 %. We also show how to apply cartographic quality measures in our method and discuss their effects on examples.}, author = {Haunert, J.-H. and Wolff, A.}, booktitle = {Proc. 18th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM SIGSPATIAL GIS '10)}, doi = {10.1145/1869790.1869819}, file = {HaunertWolff2010.pdf:http\://www1.informatik.uni-wuerzburg.de/pub/haunert/pdf/HaunertWolff2010.pdf:PDF}, pages = {192--201}, timestamp = {2011-11-07T12:01:05.000+0100}, title = {Optimal and Topologically Safe Simplification of Building Footprints}, url = {http://dl.acm.org/citation.cfm?doid=1869790.1869819}, year = {2010} }
	J.-H. Haunert, and A. Wolff. Area aggregation in map generalisation by mixed-integer programming. International Journal of Geographical Information Science, 24(12):1871-1897, 2010. abstract doi bibtex
	Topographic databases normally contain areas of different land cover classes, commonly defining a planar partition, that is, gaps and overlaps are not allowed. When reducing the scale of such a database, some areas become too small for representation and need to be aggregated. This unintentionally but unavoidably results in changes of classes. In this article we present an optimisation method for the aggregation problem. This method aims to minimise changes of classes and to create compact shapes, subject to hard constraints ensuring aggregates of sufficient size for the target scale. To quantify class changes we apply a semantic distance measure. We give a graph theoretical problem formulation and prove that the problem is NP-hard, meaning that we cannot hope to find an efficient algorithm. Instead, we present a solution by mixed-integer programming that can be used to optimally solve small instances with existing optimisation software. In order to process large datasets, we introduce specialised heuristics that allow certain variables to be eliminated in advance and a problem instance to be decomposed into independent sub-instances. We tested our method for a dataset of the official German topographic database ATKIS with input scale 1:50,000 and output scale 1:250,000. For small instances, we compare results of this approach with optimal solutions that were obtained without heuristics. We compare results for large instances with those of an existing iterative algorithm and an alternative optimisation approach by simulated annealing. These tests allow us to conclude that, with the defined heuristics, our optimisation method yields high-quality results for large datasets in modest time. doi:10.1080/13658810903401008 @article{haunertwolff2010b, abstract = {Topographic databases normally contain areas of different land cover classes, commonly defining a planar partition, that is, gaps and overlaps are not allowed. When reducing the scale of such a database, some areas become too small for representation and need to be aggregated. This unintentionally but unavoidably results in changes of classes. In this article we present an optimisation method for the aggregation problem. This method aims to minimise changes of classes and to create compact shapes, subject to hard constraints ensuring aggregates of sufficient size for the target scale. To quantify class changes we apply a semantic distance measure. We give a graph theoretical problem formulation and prove that the problem is NP-hard, meaning that we cannot hope to find an efficient algorithm. Instead, we present a solution by mixed-integer programming that can be used to optimally solve small instances with existing optimisation software. In order to process large datasets, we introduce specialised heuristics that allow certain variables to be eliminated in advance and a problem instance to be decomposed into independent sub-instances. We tested our method for a dataset of the official German topographic database ATKIS with input scale 1:50,000 and output scale 1:250,000. For small instances, we compare results of this approach with optimal solutions that were obtained without heuristics. We compare results for large instances with those of an existing iterative algorithm and an alternative optimisation approach by simulated annealing. These tests allow us to conclude that, with the defined heuristics, our optimisation method yields high-quality results for large datasets in modest time.}, author = {Haunert, J.-H. and Wolff, A.}, doi = {10.1080/13658810903401008}, file = {HaunertWolff2010b.pdf:http\://www1.informatik.uni-wuerzburg.de/pub/haunert/pdf/HaunertWolff2010b.pdf:PDF}, journal = {International Journal of Geographical Information Science}, number = {12}, pages = {1871--1897}, timestamp = {2011-11-07T12:01:05.000+0100}, title = {Area aggregation in map generalisation by mixed-integer programming}, url = {http://www.informaworld.com/smpp/content~db=all~content=a930246337~tab=content}, volume = {24}, year = {2010} }

	J.-H. Haunert, and M. Sester. Area collapse and road centerlines based on straight skeletons. GeoInformatica, 12(2):169-191, 2008. abstract doi bibtex
	Skeletonization of polygons is a technique, which is often applied to problems of cartography and geographic information science. Especially it is needed for generalization tasks such as the collapse of small or narrow areas, which are negligible for a certain scale. Different skeleton operators can be used for such tasks. One of them is the straight skeleton, which was rediscovered by computer scientists several years ago after decades of neglect. Its full range of practicability and its benefits for cartographic applications have not been revealed yet. Based on the straight skeleton an area collapse that preserves topological constraints as well as a partial area collapse can be performed. An automatic method for the derivation of road centerlines from a cadastral dataset, which uses special characteristics of the straight skeleton, is shown. doi:10.1007/s10707-007-0028-x @article{haunert2008, abstract = {Skeletonization of polygons is a technique, which is often applied to problems of cartography and geographic information science. Especially it is needed for generalization tasks such as the collapse of small or narrow areas, which are negligible for a certain scale. Different skeleton operators can be used for such tasks. One of them is the straight skeleton, which was rediscovered by computer scientists several years ago after decades of neglect. Its full range of practicability and its benefits for cartographic applications have not been revealed yet. Based on the straight skeleton an area collapse that preserves topological constraints as well as a partial area collapse can be performed. An automatic method for the derivation of road centerlines from a cadastral dataset, which uses special characteristics of the straight skeleton, is shown.}, author = {Haunert, J.-H. and Sester, M.}, doi = {10.1007/s10707-007-0028-x}, file = {HaunertSester2008.pdf:http\://www1.informatik.uni-wuerzburg.de/pub/haunert/pdf/HaunertSester2008.pdf:PDF}, journal = {GeoInformatica}, number = {2}, pages = {169--191}, timestamp = {2011-11-07T12:01:04.000+0100}, title = {Area collapse and road centerlines based on straight skeletons}, url = {http://www.springerlink.com/content/20103w9530887286/}, volume = {12}, year = {2008} }
	J.-H. Haunert, and A. Wolff. Optimal simplification of building ground plans. In volume XXXVII(Part B2) of International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences. Proc. XXIst ISPRS Congress, pages 373-378. 2008. abstract bibtex
	This paper presents an optimization approach to simplify building ground plans given by two-dimensional polygons. We define a simplified building as a subsequence of the original building edges; its vertices are defined by intersections of consecutive (and possibly extended) edges in the selected sequence. Our aim is to minimize the number of edges subject to a user-defined error tolerance. We prove that this problem is NP-hard when requiring that the output consists of non-intersecting simple polygons. Thus we cannot hope for an efficient, exact algorithm. Instead, we propose a heuristic and an integer programming formulation that can be used to solve the problem with existing optimization software. We discuss results of our algorithms and how to incorporate more sophisticated objective functions into our model. @inproceedings{haunert2008b, abstract = {This paper presents an optimization approach to simplify building ground plans given by two-dimensional polygons. We define a simplified building as a subsequence of the original building edges; its vertices are defined by intersections of consecutive (and possibly extended) edges in the selected sequence. Our aim is to minimize the number of edges subject to a user-defined error tolerance. We prove that this problem is NP-hard when requiring that the output consists of non-intersecting simple polygons. Thus we cannot hope for an efficient, exact algorithm. Instead, we propose a heuristic and an integer programming formulation that can be used to solve the problem with existing optimization software. We discuss results of our algorithms and how to incorporate more sophisticated objective functions into our model.}, author = {Haunert, J.-H. and Wolff, A.}, booktitle = {Proc. XXIst ISPRS Congress}, file = {01.pdf:http\://www.isprs.org/congresses/beijing2008/proceedings/2_pdf/3_WG-II-3/01.pdf:PDF}, organization = {ISPRS}, pages = {373--378}, series = {International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences}, timestamp = {2011-11-07T12:01:06.000+0100}, title = {Optimal simplification of building ground plans}, url = {http://www.isprs.org/proceedings/XXXVII/congress/tc2.aspx#wg3}, volume = {XXXVII(Part B2)}, year = {2008} }
	J.-H. Haunert, and M. Sester. Assuring logical consistency and semantic accuracy in map generalization. Photogrammetrie - Fernerkundung - Geoinformation (PFG), 2008(3):165-173, 2008. abstract bibtex
	In recent years national mapping agencies have increasingly integrated automatic map generalization methods in their production lines. This raises the question of how to assess and assure the quality of mapping products such as digital landscape models. Generalization must not only ensure specified standards for an output scale, but also needs to keep semantics as similar as possible under these given requirements. In order to allow for objective comparisons of different generalization results we introduce a semantic distance measure. We present results that optimize this measure subject to constraints reflecting database specifications and show how this measure can be used to compare the results of different methods, including exact and heuristic approaches. @article{haunert2008d, abstract = {In recent years national mapping agencies have increasingly integrated automatic map generalization methods in their production lines. This raises the question of how to assess and assure the quality of mapping products such as digital landscape models. Generalization must not only ensure specified standards for an output scale, but also needs to keep semantics as similar as possible under these given requirements. In order to allow for objective comparisons of different generalization results we introduce a semantic distance measure. We present results that optimize this measure subject to constraints reflecting database specifications and show how this measure can be used to compare the results of different methods, including exact and heuristic approaches.}, author = {Haunert, J.-H. and Sester, M.}, file = {HaunertPFG08.pdf:http\://www1.informatik.uni-wuerzburg.de/pub/haunert/pdf/HaunertPFG08.pdf:PDF}, journal = {Photogrammetrie - Fernerkundung - Geoinformation (PFG)}, number = {3}, pages = {165--173}, timestamp = {2011-11-07T12:01:04.000+0100}, title = {Assuring logical consistency and semantic accuracy in map generalization}, url = {http://www.dgpf.de/neu/pfg-digital/2008/Heft_3.pdf#page=17}, volume = {2008}, year = {2008} }
	M. Sester, J.-H. Haunert, and K.-H. Anders. Modell- und kartographische Generalisierung von topographischen und thematischen Informationen. Kartographische Nachrichten, 6:307-314, 2008. abstract bibtex
	Die Automation in der Generalisierung ist eine Herausforderung, der sich Wissenschaftler und Firmen seit einigen Jahren stellen. Es wurden bereits sehr gute Erfolge erzielt, die sich an der Verfügbarkeit von sehr leistungsfähigen Algorithmen ablesen lassen. Im Beitrag wird auf einige dieser Operationen eingegangen und dargestellt, wo derzeit noch offene Fragen sind und wie diese sich durch neue Ansätze lösen lassen. Besonders wird die Möglichkeit herausgestellt, den Gesamtablauf der Generalisierung als Prozess zu beschreiben, der somit nachvollziehbar und reproduzierbar wird. @article{sester2008, abstract = {Die Automation in der Generalisierung ist eine Herausforderung, der sich Wissenschaftler und Firmen seit einigen Jahren stellen. Es wurden bereits sehr gute Erfolge erzielt, die sich an der Verfügbarkeit von sehr leistungsfähigen Algorithmen ablesen lassen. Im Beitrag wird auf einige dieser Operationen eingegangen und dargestellt, wo derzeit noch offene Fragen sind und wie diese sich durch neue Ansätze lösen lassen. Besonders wird die Möglichkeit herausgestellt, den Gesamtablauf der Generalisierung als Prozess zu beschreiben, der somit nachvollziehbar und reproduzierbar wird.}, author = {Sester, M. and Haunert, J.-H. and Anders, K.-H.}, journal = {Kartographische Nachrichten}, pages = {307--314}, timestamp = {2011-11-07T12:01:06.000+0100}, title = {{M}odell- und kartographische {G}eneralisierung von topographischen und thematischen {I}nformationen}, volume = {6}, year = {2008} }

	C. Brenner, V. Paelke, J.-H. Haunert, and N. Ripperda. Das virtuelle Fernrohr GeoScope. In Unimagazin Hannover. Übers Reisen - Forschung rund um das Fernweh, pages 34-37. Leibniz Universität Hannover, 2007. abstract bibtex
	Bei der Reisevorbereitung nutzen viele bereits internetbasierte und virtuelle Darstellungen mit räumlichem Bezug: Routenplaner für die Anreise, Google Earth für die Luftansicht des Zielgebiets oder Bilder und Filme im Internet. Im Urlaub angekommen, ist die Auswahl technikbasierter Informationsmöglichkeiten eher ernüchternd und beschränkt sich nicht selten auf eine gedruckte Karte. Dabei gibt es ein sehr bekanntes technisches Gerät für den Tourismus schon sehr lange: das Münzfernrohr. Vier Wissenschaftler des Instituts für Kartographie und Geoinformatik zeigen, wie es "virtualisiert" und zur Informationsvermittlung erweitert werden kann. @incollection{brenner2007, abstract = {Bei der Reisevorbereitung nutzen viele bereits internetbasierte und virtuelle Darstellungen mit räumlichem Bezug: Routenplaner für die Anreise, Google Earth für die Luftansicht des Zielgebiets oder Bilder und Filme im Internet. Im Urlaub angekommen, ist die Auswahl technikbasierter Informationsmöglichkeiten eher ernüchternd und beschränkt sich nicht selten auf eine gedruckte Karte. Dabei gibt es ein sehr bekanntes technisches Gerät für den Tourismus schon sehr lange: das Münzfernrohr. Vier Wissenschaftler des Instituts für Kartographie und Geoinformatik zeigen, wie es "virtualisiert" und zur Informationsvermittlung erweitert werden kann.}, author = {Brenner, C. and Paelke, V. and Haunert, J.-H. and Ripperda, N.}, booktitle = {{\"U}bers {R}eisen -- {F}orschung rund um das {F}ernweh}, file = {07_1_2_34_37_brenner.pdf:http\://www.uni-hannover.de/imperia/md/content/alumni/unimagazin/2007/07_1_2_34_37_brenner.pdf:PDF}, number = {1 \& 2}, pages = {34--37}, publisher = {Leibniz Universit\"at Hannover}, series = {Unimagazin Hannover}, timestamp = {2011-11-07T12:01:00.000+0100}, title = {{D}as virtuelle {F}ernrohr {G}eo{S}cope}, year = {2007} }
	J.-H. Haunert. Optimization methods for area aggregation in land cover maps. In Proc. 23rd International Cartographic Conference (ICC'07), August 4-10, 2007, Moscow, Russia. 2007. abstract bibtex
	The aggregation of areas is an important subproblem of the map generalization task. Especially, it is relevant for the generalization of topographic maps which contain areas of different land cover, such as settlement, water, or different kinds of vegetation. An existing approach is to apply algorithms that iteratively merge adjacent areas, taking only local measures into consideration. In contrast, global optimization methods are proposed in this paper to derive maps of higher quality. Given a planar subdivision in which each area is assigned to a land cover class, we consider the problem of aggregating areas such that defined thresholds are satisfied. The aggregation is directed at two objectives: Classes of areas shall change as little as possible and compact shapes are preferred. In this paper, the problem is formalized and two different approaches are compared, namely mixed-integer programming and simulated annealing. @inproceedings{haunert2007, abstract = {The aggregation of areas is an important subproblem of the map generalization task. Especially, it is relevant for the generalization of topographic maps which contain areas of different land cover, such as settlement, water, or different kinds of vegetation. An existing approach is to apply algorithms that iteratively merge adjacent areas, taking only local measures into consideration. In contrast, global optimization methods are proposed in this paper to derive maps of higher quality. Given a planar subdivision in which each area is assigned to a land cover class, we consider the problem of aggregating areas such that defined thresholds are satisfied. The aggregation is directed at two objectives: Classes of areas shall change as little as possible and compact shapes are preferred. In this paper, the problem is formalized and two different approaches are compared, namely mixed-integer programming and simulated annealing.}, author = {Haunert, J.-H.}, booktitle = {Proc. 23rd International Cartographic Conference (ICC'07), August 4--10, 2007, Moscow, Russia}, file = {HaunertICC07.pdf:http\://www1.informatik.uni-wuerzburg.de/pub/haunert/pdf/HaunertICC07.pdf:PDF}, timestamp = {2011-11-07T12:01:01.000+0100}, title = {Optimization methods for area aggregation in land cover maps}, year = {2007} }
	J.-H. Haunert. Efficient area aggregation by combination of different techniques. In Proc. 10th ICA Workshop on Generalisation and Multiple Representation, August 2-3, 2007, Moscow, Russia. 2007. abstract bibtex
	When reducing the scale of a topographic database, some areas of the data set become too small for representation and need to be aggregated with others, unintentionally but unavoidably leading to changes of some areas' land cover classes. In this paper, we approach this problem by optimisation: Given a planar subdivision containing areas of different land cover classes, the problem is to aggregate areas into contiguous regions and to define the class for each region, such that each region satisfies a size threshold and the overall class change is minimal. A second objective is to create compact shapes. In an earlier paper we proved that the problem is NP-hard. We have presented a method by mixed-integer programming for its solution and introduced several heuristics. Our tests revealed that, even with the defined heuristics, our method does generally not allow to solve problem instances of more than 400 areas. In this paper we present a new efficient heuristic for the problem. Our approach is to locally introduce intermediate levels of details. Steps between these scales can be processed using our previously presented method. This approach allows processing large data sets a complete map sheet of the German topographic map at scale 1:50.000 was processed to meet the requirements for the scale 1:250.000. We show that our method generalizes an existing iterative algorithm for the same problem and compare the results being obtained with different settings of our method. Compared with the existing iterative algorithm, our method resulted in 27,4% less change of land cover classes. @inproceedings{haunert2007b, abstract = {When reducing the scale of a topographic database, some areas of the data set become too small for representation and need to be aggregated with others, unintentionally but unavoidably leading to changes of some areas' land cover classes. In this paper, we approach this problem by optimisation: Given a planar subdivision containing areas of different land cover classes, the problem is to aggregate areas into contiguous regions and to define the class for each region, such that each region satisfies a size threshold and the overall class change is minimal. A second objective is to create compact shapes. In an earlier paper we proved that the problem is NP-hard. We have presented a method by mixed-integer programming for its solution and introduced several heuristics. Our tests revealed that, even with the defined heuristics, our method does generally not allow to solve problem instances of more than 400 areas. In this paper we present a new efficient heuristic for the problem. Our approach is to locally introduce intermediate levels of details. Steps between these scales can be processed using our previously presented method. This approach allows processing large data sets a complete map sheet of the German topographic map at scale 1:50.000 was processed to meet the requirements for the scale 1:250.000. We show that our method generalizes an existing iterative algorithm for the same problem and compare the results being obtained with different settings of our method. Compared with the existing iterative algorithm, our method resulted in 27,4% less change of land cover classes.}, author = {Haunert, J.-H.}, booktitle = {Proc. 10th ICA Workshop on Generalisation and Multiple Representation, August 2--3, 2007, Moscow, Russia}, file = {Haunert_ICAWorkshop.pdf:http\://ica.ign.fr/BDpubli/moscow2007/Haunert_ICAWorkshop.pdf:PDF}, timestamp = {2011-11-07T12:01:01.000+0100}, title = {Efficient area aggregation by combination of different techniques}, year = {2007} }
	J.-H. Haunert. A formal model and mixed-integer program for area aggregation in map generalization. In volume XXXVI(Part 3/W49A) of International Archives of Photogrammetry, Remote Sensing and Spatial Information Sciences. Photogrammetric Image Analysis (PIA'07), September 19-21, 2007, Munich, Germany, pages 161-166. 2007. abstract bibtex
	This paper presents a model and an optimization method for a problem that appears when reducing the scale of a topographic database. Such a database commonly contains areas of different land cover classes that define a planar subdivision. When reducing its scale, some areas become too small and need to be aggregated. In order to produce contiguous aggregates that are not smaller than a user-defined threshold, it is necessary to change the classes of some areas. As generalization intends to preserve the characteristic features of the map, we aim to change classes as little as possible. A second objective is to create simple, compact shapes. Based on a previous work that neglected this second objective, we define a more general problem in this paper that reflects both aims of generalization. The problem was proven to be NP-hard, meaning that it is unlikely to find an efficient solution. Therefore, we propose a mixed-integer program (MIP) and heuristics, which enable the production of near-optimal results. The paper concludes with the presentation of some results we obtained using our method. @inproceedings{haunert2007d, abstract = {This paper presents a model and an optimization method for a problem that appears when reducing the scale of a topographic database. Such a database commonly contains areas of different land cover classes that define a planar subdivision. When reducing its scale, some areas become too small and need to be aggregated. In order to produce contiguous aggregates that are not smaller than a user-defined threshold, it is necessary to change the classes of some areas. As generalization intends to preserve the characteristic features of the map, we aim to change classes as little as possible. A second objective is to create simple, compact shapes. Based on a previous work that neglected this second objective, we define a more general problem in this paper that reflects both aims of generalization. The problem was proven to be NP-hard, meaning that it is unlikely to find an efficient solution. Therefore, we propose a mixed-integer program (MIP) and heuristics, which enable the production of near-optimal results. The paper concludes with the presentation of some results we obtained using our method.}, author = {Haunert, J.-H.}, booktitle = {Photogrammetric Image Analysis (PIA'07), September 19--21, 2007, Munich, Germany}, file = {PIA07_Haunert.pdf:http\://www.pf.bv.tum.de/isprs/pia07/puba/PIA07_Haunert.pdf:PDF}, organization = {ISPRS}, pages = {161--166}, series = {International Archives of Photogrammetry, Remote Sensing and Spatial Information Sciences}, timestamp = {2011-11-07T12:01:02.000+0100}, title = {A formal model and mixed-integer program for area aggregation in map generalization}, volume = {XXXVI(Part 3/W49A)}, year = {2007} }
	E. S. Podolskaya, K.-H. Anders, J.-H. Haunert, and M. Sester. Quality assessment for polygon generalization. In Quality Aspects in Spatial Data Mining, pages 211-220. CRC Press, Boca Raton, USA, 2007. abstract doi bibtex
	Different methods for map generalization have been developed. However, there are only a few publications that discuss the automatic quality assessment of generalized maps. This problem becomes crucial when the usefulness of a map has to be evaluated or different methods need to be compared, e.g. to find the best algorithm for a specific application. In this paper we present a new approach for the quality assessment of generalized polygons. In particular the simplification of buildings and the generalization of polygons that represent land use in a topographic database are discussed. Our approach distinguishes between two aims of generalization: Reducing the amount of data and keeping the map similar to the input map. A measure of quality that defines a compromise between these conflicting objectives is introduced. The proposed method was tested for a German cadastral data set and the official German topographic database ATKIS. doi:10.1201/9781420069273.ch16 @incollection{podolskaya2007, abstract = {Different methods for map generalization have been developed. However, there are only a few publications that discuss the automatic quality assessment of generalized maps. This problem becomes crucial when the usefulness of a map has to be evaluated or different methods need to be compared, e.g. to find the best algorithm for a specific application. In this paper we present a new approach for the quality assessment of generalized polygons. In particular the simplification of buildings and the generalization of polygons that represent land use in a topographic database are discussed. Our approach distinguishes between two aims of generalization: Reducing the amount of data and keeping the map similar to the input map. A measure of quality that defines a compromise between these conflicting objectives is introduced. The proposed method was tested for a German cadastral data set and the official German topographic database ATKIS.}, author = {Podolskaya, E. S. and Anders, K.-H. and Haunert, J.-H. and Sester, M.}, booktitle = {Quality Aspects in Spatial Data Mining}, chapter = {16}, doi = {10.1201/9781420069273.ch16}, file = {PodolskayaEtAl2007.pdf:http\://www1.informatik.uni-wuerzburg.de/pub/haunert/pdf/PodolskayaEtAl2007.pdf:PDF}, pages = {211--220}, publisher = {CRC Press, Boca Raton, USA}, timestamp = {2011-11-07T12:01:06.000+0100}, title = {Quality assessment for polygon generalization}, year = {2007} }

	C. Brenner, V. Paelke, J.-H. Haunert, and N. Ripperda. The GeoScope - a mixed-reality system for planning and public participation. In Proc. 25th Urban Data Management Symposium (UDMS'06), May 15-17, 2006, Aalborg, Denmark. 2006. abstract bibtex
	The augmentation of real environments with additional computer generated information (augmented reality, AR), and the addition of virtual contents (mixed reality, MR) are promising interaction paradigms for the support of applications outside the classical office scenario. While the potential of AR for applications such as geo-visualization has been shown using a number of demonstration systems, there are virtually no systems in daily use up to now. This is mainly due to technical reasons. Besides suitable displays, there is a lack of reliable and accurate tracking systems, which are however required for an exact registration of the virtual contents and the real scene. Additionally, there is a lack of experience and tools for the creation of mixed reality applications and often, of intuitive interaction techniques. Especially for applications involving public audience (e.g. exhibitions, museums, public participation), additional requirements apply, such as reliability, robustness, easy adaptation to different users, and the necessity for relatively low operating expenses. In this paper, we introduce the GeoScope, a mixed-reality input/output device, which addresses those problems, especially for public applications. The GeoScope is mounted at a fixed position and consists of a display, oriented towards the user, and a camera, which points at the surroundings. Just as a telescope, the GeoScope can be turned around two axes, the two angles being captured by measuring devices. Together with the known position, a fast and highly precise tracking of the current view direction is possible, allowing the superposition of the real scene, as delivered by the camera, and virtually generated information. @inproceedings{Brenner2006, abstract = {The augmentation of real environments with additional computer generated information (augmented reality, AR), and the addition of virtual contents (mixed reality, MR) are promising interaction paradigms for the support of applications outside the classical office scenario. While the potential of AR for applications such as geo-visualization has been shown using a number of demonstration systems, there are virtually no systems in daily use up to now. This is mainly due to technical reasons. Besides suitable displays, there is a lack of reliable and accurate tracking systems, which are however required for an exact registration of the virtual contents and the real scene. Additionally, there is a lack of experience and tools for the creation of mixed reality applications and often, of intuitive interaction techniques. Especially for applications involving public audience (e.g. exhibitions, museums, public participation), additional requirements apply, such as reliability, robustness, easy adaptation to different users, and the necessity for relatively low operating expenses. In this paper, we introduce the GeoScope, a mixed-reality input/output device, which addresses those problems, especially for public applications. The GeoScope is mounted at a fixed position and consists of a display, oriented towards the user, and a camera, which points at the surroundings. Just as a telescope, the GeoScope can be turned around two axes, the two angles being captured by measuring devices. Together with the known position, a fast and highly precise tracking of the current view direction is possible, allowing the superposition of the real scene, as delivered by the camera, and virtually generated information.}, author = {Brenner, C. and Paelke, V. and Haunert, J.-H. and Ripperda, N.}, booktitle = {Proc. 25th Urban Data Management Symposium (UDMS'06), May 15-17, 2006, Aalborg, Denmark}, file = {BrennerEtAl2006.pdf:http\://www1.informatik.uni-wuerzburg.de/pub/haunert/pdf/BrennerEtAl2006.pdf:PDF}, timestamp = {2011-11-07T12:01:00.000+0100}, title = {The {GeoScope} -- a mixed-reality system for planning and public participation}, year = {2006} }
	J.-H. Haunert, K.-H. Anders, and M. Sester. Hierarchical structures for rule-based incremental generalisation. In volume XXXVI(Part 2/W40) of International Archives of Photogrammetry, Remote Sensing and Spatial Information Sciences. Proc. ISPRS Workshop on Multiple Representation and Interoperability of Spatial Data, February 22-24, 2006, Hannover, Germany, pages 49-57. 2006. abstract bibtex
	Multiple Representation Databases are structures that link different data sets based on common geometry and/or semantics. They offer the possibility to realize an efficient updating process in case of changes, as only one data set has to be updated and the changes can be propagated to the linked one. There are some prerequisites for the realisation of such a functionality which are elaborated on in the paper. First of all, functional dependencies between the data sets have to be known or made explicit. Secondly, partitioning schemes of space have to be available in order to make sure that local changes can be restricted locally and do not spread over the whole data set. @inproceedings{haunert2006a, abstract = {Multiple Representation Databases are structures that link different data sets based on common geometry and/or semantics. They offer the possibility to realize an efficient updating process in case of changes, as only one data set has to be updated and the changes can be propagated to the linked one. There are some prerequisites for the realisation of such a functionality which are elaborated on in the paper. First of all, functional dependencies between the data sets have to be known or made explicit. Secondly, partitioning schemes of space have to be available in order to make sure that local changes can be restricted locally and do not spread over the whole data set.}, author = {Haunert, J.-H. and Anders, K.-H. and Sester, M.}, booktitle = {Proc. ISPRS Workshop on Multiple Representation and Interoperability of Spatial Data, February 22--24, 2006, Hannover, Germany}, file = {hannover06.pdf#page=55:http\://www.isprs.org/commission2/hannover06/hannover06.pdf#page=55:PDF}, organization = {ISPRS}, pages = {49--57}, series = {International Archives of Photogrammetry, Remote Sensing and Spatial Information Sciences}, timestamp = {2011-11-07T12:01:03.000+0100}, title = {Hierarchical structures for rule-based incremental generalisation}, volume = {XXXVI(Part 2/W40)}, year = {2006} }
	J.-H. Haunert, and A. Wolff. Generalization of land cover maps by mixed integer programming. In Proc. 14th Annual ACM International Symposium on Advances in Geographic Information Systems (ACM GIS '06), pages 75-82. 2006. abstract doi bibtex
	We present a novel method for the automatic generalization of land cover maps. A land cover map is composed of areas that collectively form a tessellation of the plane and each area is assigned to a land cover class such as lake, forest, or settlement. Our method aggregates areas into contiguous regions of equal class and of size greater than a user-defined threshold. To achieve this goal, some areas need to be enlarged at the expense of others. Given function that defines costs for the transformation between pairs of classes, our method guarantees to return a solution of minimal total cost. The method is based on a mixed integer program (MIP). To process maps with more than 50 areas, heuristics are introduced that lead to an alternative MIP formulation. The effects of the heuristics on the obtained solution and the computation time are discussed. The methods were tested using real data from the official German topographic data set (ATKIS) at scales 1:50.000 and 1:250.000. doi:10.1145/1183471.1183485 @inproceedings{haunert2006b, abstract = {We present a novel method for the automatic generalization of land cover maps. A land cover map is composed of areas that collectively form a tessellation of the plane and each area is assigned to a land cover class such as lake, forest, or settlement. Our method aggregates areas into contiguous regions of equal class and of size greater than a user-defined threshold. To achieve this goal, some areas need to be enlarged at the expense of others. Given function that defines costs for the transformation between pairs of classes, our method guarantees to return a solution of minimal total cost. The method is based on a mixed integer program (MIP). To process maps with more than 50 areas, heuristics are introduced that lead to an alternative MIP formulation. The effects of the heuristics on the obtained solution and the computation time are discussed. The methods were tested using real data from the official German topographic data set (ATKIS) at scales 1:50.000 and 1:250.000.}, author = {Haunert, J.-H. and Wolff, A.}, booktitle = {Proc. 14th Annual ACM International Symposium on Advances in Geographic Information Systems (ACM GIS '06)}, doi = {10.1145/1183471.1183485}, file = {HaunertWolff2006.pdf:http\://www1.informatik.uni-wuerzburg.de/pub/haunert/pdf/HaunertWolff2006.pdf:PDF}, isbn = {1-59593-529-0}, location = {Arlington, Virginia, USA}, pages = {75--82}, timestamp = {2011-11-07T12:01:05.000+0100}, title = {Generalization of land cover maps by mixed integer programming}, url = {http://doi.acm.org/10.1145/1183471.1183485}, year = {2006} }
	J.-H. Haunert. Aktualisierung von Geodaten in einer Multiple Representation Database. In Publikationen der Deutschen Gesellschaft für Photogrammetrie, Fernerkundung und Geoinformation e.V., DGPF Jahrestagung 2006, Berlin, Germany. 2006. abstract bibtex
	In zunehmendem Maße werden topographische Datensätze unterschiedlicher Maßstäbe in einer gemeinsamen Datenbank gehalten. Die Fortführung der Daten innerhalb einer solchen Datenbank ist ein aktuelles Problem der Geoinformatik. Im Allgemeinen wird, ausgehend von einem Quelldatensatz, eine Propagierung von Information in einen Zieldatensatz geringerer Auflösung mittels Generalisierung angestrebt. In der Kartographie wird die Landschaft üblicherweise in Flächen unterschiedlicher Landnut-zungs- und Vegetationsklassen gegliedert. Die Aggregation dieser Flächen ist eine wichtige Aufgabe der Modellgeneralisierung. In diesem Beitrag wird ein iteratives Aggregationsverfahren, welches lokale Beziehungen zwischen Objekten berücksichtigt, einem globalen Optimierungsverfahren gegenübergestellt. Die Möglichkeiten zum Einsatz der Verfahren für die Fortführung werden diskutiert. @inproceedings{haunert2006c, abstract = {In zunehmendem Maße werden topographische Datensätze unterschiedlicher Maßstäbe in einer gemeinsamen Datenbank gehalten. Die Fortführung der Daten innerhalb einer solchen Datenbank ist ein aktuelles Problem der Geoinformatik. Im Allgemeinen wird, ausgehend von einem Quelldatensatz, eine Propagierung von Information in einen Zieldatensatz geringerer Auflösung mittels Generalisierung angestrebt. In der Kartographie wird die Landschaft üblicherweise in Flächen unterschiedlicher Landnut-zungs- und Vegetationsklassen gegliedert. Die Aggregation dieser Flächen ist eine wichtige Aufgabe der Modellgeneralisierung. In diesem Beitrag wird ein iteratives Aggregationsverfahren, welches lokale Beziehungen zwischen Objekten berücksichtigt, einem globalen Optimierungsverfahren gegenübergestellt. Die Möglichkeiten zum Einsatz der Verfahren für die Fortführung werden diskutiert.}, author = {Haunert, J.-H.}, booktitle = {Publikationen der Deutschen Gesellschaft f\"ur Photogrammetrie, Fernerkundung und Geoinformation e.V., DGPF Jahrestagung 2006, Berlin, Germany}, file = {HaunertDGPF06.pdf:http\://www1.informatik.uni-wuerzburg.de/pub/haunert/pdf/HaunertDGPF06.pdf:PDF}, timestamp = {2011-11-07T12:01:02.000+0100}, title = {Aktualisierung von {Geodaten} in einer {M}ultiple {R}epresentation {D}atabase}, year = {2006} }

	J.-H. Haunert, C. Brenner, and H. Neidhart. Using a geographic information system for the generation of driving simulator scenes. Advances in Transportation Studies - An International Journal, Special Issue:33-44, 2005. abstract bibtex
	Driving simulators often require a linear description of scenes in terms of events which happen at specified locations. This concept is very sensible for the actual simulation, since it not only saves space, but also makes simulations repeatable. Since maneuverability is essentially constrained to one dimension, test persons will encounter the very same scenes and challenges during the simulation. However, defining scenes with a reasonable complexity or even scenes resembling real world situations is very elaborate. Furthermore, scene reuse is not supported very well, since cutting and pasting of linear scene descriptions requires a considerable ability to imagine the actual scenes being manipulated. In this paper, we show how Geographic Information Systems (GIS) can be used to define, visualize, and manage scene descriptions for a simulator system. To that end, we have chosen ArcGIS from ESRI, Inc. for the GIS part and STISIM drive from Systems Technology, Inc. for the simulator part. One key characteristic of the approach is that rather than putting the entire effort into building individual simulator scenes, one builds simulator worlds, from which later different simulator scenes can be derived with little effort. @article{haunert2005, abstract = {Driving simulators often require a linear description of scenes in terms of events which happen at specified locations. This concept is very sensible for the actual simulation, since it not only saves space, but also makes simulations repeatable. Since maneuverability is essentially constrained to one dimension, test persons will encounter the very same scenes and challenges during the simulation. However, defining scenes with a reasonable complexity or even scenes resembling real world situations is very elaborate. Furthermore, scene reuse is not supported very well, since cutting and pasting of linear scene descriptions requires a considerable ability to imagine the actual scenes being manipulated. In this paper, we show how Geographic Information Systems (GIS) can be used to define, visualize, and manage scene descriptions for a simulator system. To that end, we have chosen ArcGIS from ESRI, Inc. for the GIS part and STISIM drive from Systems Technology, Inc. for the simulator part. One key characteristic of the approach is that rather than putting the entire effort into building individual simulator scenes, one builds simulator worlds, from which later different simulator scenes can be derived with little effort.}, author = {Haunert, J.-H. and Brenner, C. and Neidhart, H.}, file = {HaunertSTISIM05.pdf:http\://www1.informatik.uni-wuerzburg.de/pub/haunert/pdf/HaunertSTISIM05.pdf:PDF}, journal = {Advances in Transportation Studies - An International Journal}, pages = {33--44}, timestamp = {2011-11-07T12:01:03.000+0100}, title = {Using a geographic information system for the generation of driving simulator scenes}, url = {http://host.uniroma3.it/riviste/ats/journal_page_special%20issue%202005.htm}, volume = {Special Issue}, year = {2005} }
	J.-H. Haunert. Link based conflation of geographic datasets. In Proc. 8th ICA Workshop on Generalisation and Multiple Representation. 2005. abstract bibtex
	The conflation of geographic data from different sources is an important research area in geographic information sciences. In recent time this is increasingly motivated by the demand for a higher usability of expensively collected data on the part of the national mapping agencies. For this reason also the linkage of geographic datasets with different scales and their mutual administration in one database is under examination. Linking objects of different scales will ease the propagation of new information to a generalized dataset and the transfer of information from lower to higher scale becomes more feasible. In this paper a method for a topological consistent transfer of features is presented, which assumes, that links between corresponding features exist. The method is based on a map transformation which considers locally existing geometric differences between the two involved datasets. Even though algorithms and mathematical formulas of similar existing methods differ among each other and in relation to the presented work, the term rubber sheeting is often used for this kind of transformation and will also be used here. It refers to the illustration of the map as a flexible membrane that is fitted into a frame and hence is forced to become deformed. Rubber sheeting can be implemented by an interpolation of coordinate differences that are given for control points. In this work an infinite number of control points on corresponding linear elements is defined. After an overview on related work, this paper addresses how the transformation can be set up by exploiting links between linear features. Also the mathematical foundations for the transformation are explained and results for existing datasets are shown. In the conclusion limits are presented that require further development and research. @inproceedings{haunert2005a, abstract = {The conflation of geographic data from different sources is an important research area in geographic information sciences. In recent time this is increasingly motivated by the demand for a higher usability of expensively collected data on the part of the national mapping agencies. For this reason also the linkage of geographic datasets with different scales and their mutual administration in one database is under examination. Linking objects of different scales will ease the propagation of new information to a generalized dataset and the transfer of information from lower to higher scale becomes more feasible. In this paper a method for a topological consistent transfer of features is presented, which assumes, that links between corresponding features exist. The method is based on a map transformation which considers locally existing geometric differences between the two involved datasets. Even though algorithms and mathematical formulas of similar existing methods differ among each other and in relation to the presented work, the term rubber sheeting is often used for this kind of transformation and will also be used here. It refers to the illustration of the map as a flexible membrane that is fitted into a frame and hence is forced to become deformed. Rubber sheeting can be implemented by an interpolation of coordinate differences that are given for control points. In this work an infinite number of control points on corresponding linear elements is defined. After an overview on related work, this paper addresses how the transformation can be set up by exploiting links between linear features. Also the mathematical foundations for the transformation are explained and results for existing datasets are shown. In the conclusion limits are presented that require further development and research.}, author = {Haunert, J.-H.}, booktitle = {Proc. 8th ICA Workshop on Generalisation and Multiple Representation}, file = {HaunertMapGen05.pdf:http\://www1.informatik.uni-wuerzburg.de/pub/haunert/pdf/HaunertMapGen05.pdf:PDF}, timestamp = {2011-11-07T12:01:02.000+0100}, title = {Link based conflation of geographic datasets}, year = {2005} }
	J.-H. Haunert, and M. Sester. Propagating updates between linked data sets of different scale. In Proc. 22nd International Cartographic Conference (ICC'05), July 11-16, 2005, Spain. 2005. abstract bibtex
	This work shows an incremental approach for the propagation of updates from a topographic source dataset to a generalised dataset. It aims at the result that is equal to the complete generalisation of the source dataset. For this the information from links that express correspondences of features, the knowledge of the generalisation rules and the topology of the features are considered. The problem is discussed extensively for the case of the aggregation of areas, which is based on rules that take thematic and geometrical criteria into account. Results for the generalisation of an existing dataset are shown. For the incremental method it is considered, that the update of a single feature can have different impacts on the target dataset when following the rules. An algorithm is described which is based on the derivation of the influence area on which the update is restricted. @inproceedings{haunert2005b, abstract = {This work shows an incremental approach for the propagation of updates from a topographic source dataset to a generalised dataset. It aims at the result that is equal to the complete generalisation of the source dataset. For this the information from links that express correspondences of features, the knowledge of the generalisation rules and the topology of the features are considered. The problem is discussed extensively for the case of the aggregation of areas, which is based on rules that take thematic and geometrical criteria into account. Results for the generalisation of an existing dataset are shown. For the incremental method it is considered, that the update of a single feature can have different impacts on the target dataset when following the rules. An algorithm is described which is based on the derivation of the influence area on which the update is restricted.}, author = {Haunert, J.-H. and Sester, M.}, booktitle = {Proc. 22nd International Cartographic Conference (ICC'05), July 11--16, 2005, Spain}, file = {HaunertICC05.pdf:http\://www1.informatik.uni-wuerzburg.de/pub/haunert/pdf/HaunertICC05.pdf:PDF}, timestamp = {2011-11-07T12:01:04.000+0100}, title = {Propagating updates between linked data sets of different scale}, year = {2005} }
	J.-H. Haunert. Geometrietypwechsel in einer Multi-Resolution-Datenbank. In Mitteilungen des Bundesamtes für Kartographie und Geodäsie, Band 34: Arbeitsgruppe Automation in der Kartographie - Tagung 2004. Verlag des Bundesamtes für Kartographie und Geodäsie, Frankfurt am Main, Germany, 2005. abstract bibtex
	Die gemeinsame Haltung von kartographischen Datensätzen unterschiedlicher Maßstäbe in einer Datenbank stellt eine neue Herausforderung in der Kartographie und Geoinformatik dar. Die Motivation dazu ergibt sich aus dem Bedarf an einem schnellen und dynamischen Zoom für die Web-Kartographie oder einem effektiven Verfahren für die Fortführung der Datenbestände. Es wurden Datenmodelle vorgeschlagen, in denen Zuordnungen zwischen homologen Objekten explizit beschrieben werden. Teilweise wurden die entwickelten Konzepte bereits umgesetzt. Für die Fortführung der Daten innerhalb einer solchen Datenbank fehlen allerdings noch Verfahren. Im Allgemeinen wird, ausgehend von einem Quelldatensatz, eine Propagierung von Information in einen Zieldatensatz geringerer Auflösung angestrebt. Diese Aufgabenstellung ist ein Problem der Modellgeneralisierung. In dieser Arbeit wird ein Skelettalgorithmus dargestellt, der hierzu den Geometrietypwechsel von einer flächenhaften zu einer linienförmigen Repräsentation leistet. Es werden Beispiele für den Einsatz des Algorithmus und Modifikationen für besondere Problemstellungen vorgestellt. @incollection{haunert2005c, abstract = {Die gemeinsame Haltung von kartographischen Datensätzen unterschiedlicher Maßstäbe in einer Datenbank stellt eine neue Herausforderung in der Kartographie und Geoinformatik dar. Die Motivation dazu ergibt sich aus dem Bedarf an einem schnellen und dynamischen Zoom für die Web-Kartographie oder einem effektiven Verfahren für die Fortführung der Datenbestände. Es wurden Datenmodelle vorgeschlagen, in denen Zuordnungen zwischen homologen Objekten explizit beschrieben werden. Teilweise wurden die entwickelten Konzepte bereits umgesetzt. Für die Fortführung der Daten innerhalb einer solchen Datenbank fehlen allerdings noch Verfahren. Im Allgemeinen wird, ausgehend von einem Quelldatensatz, eine Propagierung von Information in einen Zieldatensatz geringerer Auflösung angestrebt. Diese Aufgabenstellung ist ein Problem der Modellgeneralisierung. In dieser Arbeit wird ein Skelettalgorithmus dargestellt, der hierzu den Geometrietypwechsel von einer flächenhaften zu einer linienförmigen Repräsentation leistet. Es werden Beispiele für den Einsatz des Algorithmus und Modifikationen für besondere Problemstellungen vorgestellt.}, author = {Haunert, J.-H.}, booktitle = {Mitteilungen des Bundesamtes f\"ur Kartographie und Geodäsie, Band 34: Arbeitsgruppe Automation in der Kartographie -- Tagung 2004}, file = {HaunertAGA05.pdf:http\://www1.informatik.uni-wuerzburg.de/pub/haunert/pdf/HaunertAGA05.pdf:PDF}, publisher = {Verlag des Bundesamtes f\"ur Kartographie und Geodäsie, Frankfurt am Main, Germany}, timestamp = {2011-11-07T12:01:02.000+0100}, title = {Geometrietypwechsel in einer {M}ulti-{R}esolution-{D}atenbank}, year = {2005} }

	K.-H. Anders, and J.-H. Haunert. MRDB to connect 3D city models, cadastral, and topographic data together. In Proc. 24th Urban Data Management Symposium (UDMS'04), October 27-29, 2004, Chioggia (Venice), Italy. 2004. abstract bibtex
	A Multi-resolution/representation-database (MRDB) can be described as a spatial database, which can be used to store the same real-world-phenomena at different levels of precision, accuracy and resolution. Furthermore these phenomena can be stored in different ways of presentation or symbolisation. There are several reasons for introducing an MRDB: On the one hand it allows a multi-scale analysis of the data: Information in one resolution can be analysed with respect to information given in another resolution. On the other hand a major reason for National Mapping Agencies to investigate and implement MRDB is the possibility of propagating updates between the scales, which is also called incremental generalisation. In a cooperation with the German Federal Agency for Cartography and Geodesy (BKG) we are developing at the institute of cartography and geoinformatics (ikg) an automatic model generalisation und update (data revision) system for the German ATKIS (Authoritative Topographic-Cartographic Information System). In this paper we will describe the structure and functionality of our ATKIS MRDB, and the planed extension to store cadastral and 3D building information. @inproceedings{anders2004b, abstract = {A Multi-resolution/representation-database (MRDB) can be described as a spatial database, which can be used to store the same real-world-phenomena at different levels of precision, accuracy and resolution. Furthermore these phenomena can be stored in different ways of presentation or symbolisation. There are several reasons for introducing an MRDB: On the one hand it allows a multi-scale analysis of the data: Information in one resolution can be analysed with respect to information given in another resolution. On the other hand a major reason for National Mapping Agencies to investigate and implement MRDB is the possibility of propagating updates between the scales, which is also called incremental generalisation. In a cooperation with the German Federal Agency for Cartography and Geodesy (BKG) we are developing at the institute of cartography and geoinformatics (ikg) an automatic model generalisation und update (data revision) system for the German ATKIS (Authoritative Topographic-Cartographic Information System). In this paper we will describe the structure and functionality of our ATKIS MRDB, and the planed extension to store cadastral and 3D building information.}, author = {Anders, K.-H. and Haunert, J.-H.}, booktitle = {Proc. 24th Urban Data Management Symposium (UDMS'04), October 27--29, 2004, Chioggia (Venice), Italy}, timestamp = {2011-11-07T12:01:00.000+0100}, title = {{MRDB} to connect {3D} city models, cadastral, and topographic data together}, year = {2004} }
	J.-H. Haunert, and M. Sester. Using the straight skeleton for generalisation in a multiple representation environment. In Proc. 7th ICA Workshop on Generalisation and Multiple Representation, August 20-21, 2004, Leicester, UK. 2004. abstract bibtex
	In recent time a lot of research has been done towards the comprehensive administration of geographic data of different scales and thematic domains. A promising approach is the use of a Multiple Representation Database (MRDB) in which links between corresponding objects are explicitly modelled. The advantage of this approach is a limitation of redundancies and inconsistencies. It can be expected that this comprehensive administration of different data sets supports complex analysis and eases the updating process (Sester et al. 1998). Our aim is to build up a framework enabling the automatic update of features in an MRDB. We envision a system which is able to propagate information into the other representations in the database when a feature is added to an arbitrary level. To meet this demand algorithms are needed which are able to perform the generalisation of the added data considering the embedding context. The algorithms needed for generalisation depend on the relationships between objects in adjacent scale levels. The main relation is the aggregation, however, there are also more complex ones. Two of these cases are area collapses and geometry type changes. This also includes partial geometry type changes. The paper is organized as follows: after a review of related work, the relationships between objects in different scales are briefly analyzed in section 2. The main focus of the paper lies, however, in the presentation of a skeleton algorithm that can be applied to solve this task for the generalisation cases area collapse and geometry type changes from area to line. In this work the Straight Skeleton is used. The algorithm and its application to generalisation is presented in section 3. In section 4 first ideas are presented how this generalisation method can be used for the propagation of updates in MRDB. A summary concludes the paper. @inproceedings{haunert2004, abstract = {In recent time a lot of research has been done towards the comprehensive administration of geographic data of different scales and thematic domains. A promising approach is the use of a Multiple Representation Database (MRDB) in which links between corresponding objects are explicitly modelled. The advantage of this approach is a limitation of redundancies and inconsistencies. It can be expected that this comprehensive administration of different data sets supports complex analysis and eases the updating process (Sester et al. 1998). Our aim is to build up a framework enabling the automatic update of features in an MRDB. We envision a system which is able to propagate information into the other representations in the database when a feature is added to an arbitrary level. To meet this demand algorithms are needed which are able to perform the generalisation of the added data considering the embedding context. The algorithms needed for generalisation depend on the relationships between objects in adjacent scale levels. The main relation is the aggregation, however, there are also more complex ones. Two of these cases are area collapses and geometry type changes. This also includes partial geometry type changes. The paper is organized as follows: after a review of related work, the relationships between objects in different scales are briefly analyzed in section 2. The main focus of the paper lies, however, in the presentation of a skeleton algorithm that can be applied to solve this task for the generalisation cases area collapse and geometry type changes from area to line. In this work the Straight Skeleton is used. The algorithm and its application to generalisation is presented in section 3. In section 4 first ideas are presented how this generalisation method can be used for the propagation of updates in MRDB. A summary concludes the paper.}, author = {Haunert, J.-H. and Sester, M.}, booktitle = {Proc. 7th ICA Workshop on Generalisation and Multiple Representation, August 20--21, 2004, Leicester, UK}, file = {HaunertMapGen04.pdf:http\://www1.informatik.uni-wuerzburg.de/pub/haunert/pdf/HaunertMapGen04.pdf:PDF}, timestamp = {2011-11-07T12:01:05.000+0100}, title = {Using the straight skeleton for generalisation in a multiple representation environment}, year = {2004} }