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

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 = {0},
    pages = {1-25},
    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 = {0},
    year = {2023}
}

doi:https://doi.org/10.3390/rs15143495

@article{Mohseni2023,
    author = {Mohseni, Farzane and Amani, Meisam and Mohammadpour, Pegah and Kakooei, Mohammad and Jin, Shuanggen and Moghimi, Armin},
    doi = {https://doi.org/10.3390/rs15143495},
    journal = {Remote Sensing},
    number = {14},
    pages = {3495},
    title = {Wetland Mapping in Great Lakes Using Sentinel-1/2 Time-Series Imagery and DEM Data in Google Earth Engine},
    volume = {15},
    year = {2023}
}

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

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

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

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

doi:10.1080/00087041.2023.2284436

@article{forsch2023metrochrones,
    author = {Forsch,Axel and Haunert,Jan-Henrik},
    doi = {10.1080/00087041.2023.2284436},
    journal = {The Cartographic Journal},
    note = {Accepted for publication on 12th November 2023.},
    number = {-},
    pages = {-},
    title = {Metrochrones: Schematic Isochrones for Schematic Metro Maps},
    volume = {-},
    year = {2023}
}

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

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

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

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

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

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

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

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

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

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