We study the problem of aggregating a set of polygons by covering them with disjoint representative regions, thereby inducing a clustering of the polygons. Equivalently, this can be seen as a fence enclosure problem, where the goal is to surround the polygons with a set of closed curves. Our objective is to minimize a weighted sum of the total area and the total perimeter of the regions, which naturally extends other fencing problems and has applications in geographical information systems. Previously, this objective was only studied in a restricted variant, in which the boundary curves of the regions must be selected from a fixed subdivision of the plane. It is natural to ask whether the problem is still tractable if this restriction is removed, allowing output regions to be bounded by arbitrary curves. We provide a positive answer in the form of an algorithm with runtime Õ(n⁴), where n is the number of input vertices. To achieve this, we fully characterize the optimal solutions by showing that their boundaries are composed of input edges and circular arcs of constant radius. Additionally, we consider the parametric problem, where for every weighting factor we seek a solution that is optimal for that trade-off of area and perimeter. We show that 𝒪 combinatorial solutions suffice to describe all optimal solutions across all weighting factors, and provide both an exact algorithm and an approximation scheme. To make the algorithms scalable in practice, we develop engineering techniques that exploit structural properties of the solutions. Our experimental evaluation on real-world data shows linear runtime in practice, even for the parametric variant.

doi:10.4230/LIPIcs.ESA.2026.11

@inproceedings{blank2026arbitraryBicriteriaShapes,
    abstract = {We study the problem of aggregating a set of polygons by covering them with disjoint representative regions, thereby inducing a clustering of the polygons. Equivalently, this can be seen as a fence enclosure problem, where the goal is to surround the polygons with a set of closed curves. Our objective is to minimize a weighted sum of the total area and the total perimeter of the regions, which naturally extends other fencing problems and has applications in geographical information systems. Previously, this objective was only studied in a restricted variant, in which the boundary curves of the regions must be selected from a fixed subdivision of the plane. It is natural to ask whether the problem is still tractable if this restriction is removed, allowing output regions to be bounded by arbitrary curves. We provide a positive answer in the form of an algorithm with runtime Õ(n⁴), where n is the number of input vertices. To achieve this, we fully characterize the optimal solutions by showing that their boundaries are composed of input edges and circular arcs of constant radius. Additionally, we consider the parametric problem, where for every weighting factor we seek a solution that is optimal for that trade-off of area and perimeter. We show that 𝒪 combinatorial solutions suffice to describe all optimal solutions across all weighting factors, and provide both an exact algorithm and an approximation scheme. To make the algorithms scalable in practice, we develop engineering techniques that exploit structural properties of the solutions. Our experimental evaluation on real-world data shows linear runtime in practice, even for the parametric variant.},
    address = {Dagstuhl, Germany},
    author = {Blank, Lotte and Eppstein, David and Haunert, Jan-Henrik and Haverkort, Herman and Kolbe, Benedikt and Mayer, Philip and Mutzel, Petra and Naumann, Alexander and Sauer, Jonas},
    booktitle = {34th Annual European Symposium on Algorithms (ESA 2026)},
    doi = {10.4230/LIPIcs.ESA.2026.11},
    editor = {Bille, Philip and Pettie, Seth and Storandt, Sabine},
    isbn = {978-3-95977-445-1},
    issn = {1868-8969},
    pages = {11:1--11:23},
    publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
    series = {Leibniz International Proceedings in Informatics (LIPIcs)},
    title = {Bicriteria Polygon Aggregation with Arbitrary Shapes},
    url = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2026.11},
    urn = {urn:nbn:de:0030-drops-271472},
    volume = {388},
    year = {2026}
}

Measuring the similarity of polygons is a recurring challenge in numerous disciplines. In this work, we focus on the geoinformation domain, where many methods have been proposed to compare building footprints. However, they share key limitations: they typically only compare polygon boundaries, rely on heuristic alignment procedures, and yield a single global similarity score. As a result, they provide little insight into how local sub-structures correspond between polygons. To address these shortcomings, we propose geomGMD, a geometric graph mapping distance. Applied to polygonal skeletons, such as the medial axis, geomGMD produces both a global similarity value and a mapping of local sub-structures, while remaining invariant under translation and rotation. The method is particularly well-suited for building footprints, which are inherently modular polygons composed of sub-structures such as extensions and courtyards. We prove that geomGMD is a metric and derive a binary linear programming formulation for computing it. To assess its practical applicability, we evaluate geomGMD on real-world building footprint data, benchmarking it against multiple state-of-the art methods, and employing it as a core measure in a clustering task. Our method outperforms existing approaches in capturing local structural correspondences and provides richer, more interpretable similarity information. Despite the theoretical hardness of the underlying optimization problem, our model proves to scale well in practice: of more than 130 million distance computations, only 0.02% exceeded a five-minute time limit.

@article{naumann2026footprintAggEdgeOrientation,
    abstract = {Measuring the similarity of polygons is a recurring challenge in numerous disciplines. In this work, we focus on the geoinformation domain, where many methods have been proposed to compare building footprints. However, they share key limitations: they typically only compare polygon boundaries, rely on heuristic alignment procedures, and yield a single global similarity score. As a result, they provide little insight into how local sub-structures correspond between polygons. To address these shortcomings, we propose geomGMD, a geometric graph mapping distance. Applied to polygonal skeletons, such as the medial axis, geomGMD produces both a global similarity value and a mapping of local sub-structures, while remaining invariant under translation and rotation. The method is particularly well-suited for building footprints, which are inherently modular polygons composed of sub-structures such as extensions and courtyards. We prove that geomGMD is a metric and derive a binary linear programming formulation for computing it. To assess its practical applicability, we evaluate geomGMD on real-world building footprint data, benchmarking it against multiple state-of-the art methods, and employing it as a core measure in a clustering task. Our method outperforms existing approaches in capturing local structural correspondences and provides richer, more interpretable similarity information. Despite the theoretical hardness of the underlying optimization problem, our model proves to scale well in practice: of more than 130 million distance computations, only 0.02% exceeded a five-minute time limit.},
    address = {New York, NY, USA},
    author = {Bülte, Laura and Naumann, Alexander and Schlurmann, Johanna and Haunert, Jan-Henrik and Mutzel, Petra},
    doi = {},
    journal = {SIGSPATIAL '26: Proceedings of the 34th ACM International Conference on Advances in Geographic Information Systems},
    note = {Accepted for Publication.},
    pages = {},
    publisher = {Association for Computing Machinery},
    title = {geomGMD: Translation- and Rotation-Invariant Geometric Graph Mapping Distance for Building Footprint Similarity},
    volume = {},
    year = {2026}
}

The increasing availability of multi-temporal building footprint datasets has created new opportunities for studying urban development over time. A key prerequisite for many tasks in urban analytics and temporal map generalization is the aggregation of building footprints into coherent settlement regions. However, dedicated geometry-based methods for temporal aggregation remain unexplored. In the static, non-temporal setting, the bicriteria shapes framework offers an optimization-based approach: It constructs a subdivision of the plane based on the input building footprints. Then, it adds cells from the subdivision to the input to produce aggregated representative regions that are optimal with respect to a geometric objective function. We extend this framework to the temporal setting. To guide the design and evaluation of temporal methods, we identify four desirable properties: temporal consistency, scale consistency, geometric faithfulness, and efficiency. Based on these criteria, we propose several temporal subdivision schemes, integrate them with bicriteria shapes and analyze their strengths and weaknesses both theoretically and experimentally. Our experimental analysis is performed on real-world datasets from OpenStreetMap and the GHS-OBAT project. In addition, we provide an interactive visualization tool that enables direct exploration and comparison of the resulting temporal aggregations.

doi:10.1145/3841645.3844182

@article{naumann2026footprintAggEdgeOrientation,
    abstract = {The increasing availability of multi-temporal building footprint datasets has created new opportunities for studying urban development over time. A key prerequisite for many tasks in urban analytics and temporal map generalization is the aggregation of building footprints into coherent settlement regions. However, dedicated geometry-based methods for temporal aggregation remain unexplored. In the static, non-temporal setting, the bicriteria shapes framework offers an optimization-based approach: It constructs a subdivision of the plane based on the input building footprints. Then, it adds cells from the subdivision to the input to produce aggregated representative regions that are optimal with respect to a geometric objective function. We extend this framework to the temporal setting. To guide the design and evaluation of temporal methods, we identify four desirable properties: temporal consistency, scale consistency, geometric faithfulness, and efficiency. Based on these criteria, we propose several temporal subdivision schemes, integrate them with bicriteria shapes and analyze their strengths and weaknesses both theoretically and experimentally. Our experimental analysis is performed on real-world datasets from OpenStreetMap and the GHS-OBAT project. In addition, we provide an interactive visualization tool that enables direct exploration and comparison of the resulting temporal aggregations.},
    address = {New York, NY, USA},
    author = {Mayer, Philip and Naumann, Alexander and Roth, Felix and Bonerath, Annika and Sauer, Jonas and Mutzel, Petra and Haunert, Jan-Henrik},
    doi = {10.1145/3841645.3844182},
    journal = {SIGSPATIAL '26: Proceedings of the 34th ACM International Conference on Advances in Geographic Information Systems},
    note = {Accepted for Publication.},
    pages = {},
    publisher = {Association for Computing Machinery},
    title = {Temporally Consistent Aggregation of Building Footprints},
    volume = {},
    year = {2026}
}

Establishing sustainable agricultural systems while ensuring food security has become a global priority. Meeting this goal requires contributions from different fields of agricultural science, many of which depend on detailed information on crops. Recent advancements in deep learning and the transnational harmonization of administrative data have led to the availability of ever-larger datasets of agricultural field polygons. These datasets, however, vary in quality and level of detail. To achieve synergies between different information sources through data fusion and to evaluate the quality of model outputs, it is essential to efficiently identify correspondences in spatially overlapping datasets. We address this challenge by leveraging a state-of-the-art matching algorithm that we adapt by redesigning its connected-component decomposition to handle large-scale datasets of agricultural field polygons. We demonstrate the algorithm’s suitability through two case studies. First, we show how automatically delineated field polygons can be validated against ground truth in terms of their spatial quality. Second, we explore how two established reference datasets align both thematically and spatially. We discuss the dataset comparisons using different evaluation metrics and provide an interactive map viewer that enables the exploration of spatial patterns of the datasets’ alignment by visualizing matching qualities in the geographic context.

doi:10.1080/17538947.2026.2632420

@article{naumann2026aggMatching,
    abstract = {Establishing sustainable agricultural systems while ensuring food security has become a global priority. Meeting this goal requires contributions from different fields of agricultural science, many of which depend on detailed information on crops. Recent advancements in deep learning and the transnational harmonization of administrative data have led to the availability of ever-larger datasets of agricultural field polygons. These datasets, however, vary in quality and level of detail. To achieve synergies between different information sources through data fusion and to evaluate the quality of model outputs, it is essential to efficiently identify correspondences in spatially overlapping datasets. We address this challenge by leveraging a state-of-the-art matching algorithm that we adapt by redesigning its connected-component decomposition to handle large-scale datasets of agricultural field polygons.
We demonstrate the algorithm’s suitability through two case studies. First, we show how automatically delineated field polygons can be validated against ground truth in terms of their spatial quality. Second, we explore how two established reference datasets align both thematically and spatially.
We discuss the dataset comparisons using different evaluation metrics and provide an interactive map viewer that enables the exploration of spatial patterns of the datasets’ alignment by visualizing matching qualities in the geographic context.},
    author = {Naumann, Alexander and Gedicke, Sven and Haunert, Jan-Henrik},
    doi = {10.1080/17538947.2026.2632420},
    journal = {International Journal of Digital Earth},
    number = {1},
    pages = {2632420},
    title = {A {S}calable {M}atching {A}pproach for the {C}omparison of {A}gricultural {L}and {U}se {M}aps {B}ased on {C}orresponding {F}ield {P}olygons},
    volume = {19},
    year = {2026}
}

The aggregation of building footprints is a key task of cartographic generalization, which is an important topic in geoinformation science. It has been approached from various angles, ranging from heuristics and optimization algorithms to machine learning. Given a set of input polygons that represent the building footprints, the task is to generate a set of polygons that provide a coarser representation of the input. The problem has applications in the visualization of settlement areas in small-scale maps, as well as settlement classification and analysis. A popular solution approach is to construct a subdivision of the plane and then build a solution by selecting faces from the subdivision. Often, a triangulation is used for the subdivision. However, this can cause the orientations of the boundary edges in the solution to differ drastically from the input polygons, which leads to a loss of information about the underlying settlement structure. We explore an alternative method that constructs the subdivision by extending the input building edges, thereby automatically preserving their orientations. To make the approach scalable to large instances without substantially decreasing the solution quality, we propose different methods of reducing the complexity of the subdivision. Our experimental evaluation on real-world data shows that our method is able to aggregate towns containing up to ≈ 10 000 building footprints while preserving input edge orientations much better than state-of-the-art methods.

doi:10.5194/isprs-annals-XI-4-2026-153-2026

@article{naumann2026footprintAggEdgeOrientation,
    abstract = {The aggregation of building footprints is a key task of cartographic generalization, which is an important topic in geoinformation science. It has been approached from various angles, ranging from heuristics and optimization algorithms to machine learning. Given a set of input polygons that represent the building footprints, the task is to generate a set of polygons that provide a coarser representation of the input. The problem has applications in the visualization of settlement areas in small-scale maps, as well as settlement classification and analysis. A popular solution approach is to construct a subdivision of the plane and then build a solution by selecting faces from the subdivision. Often, a triangulation is used for the subdivision. However, this can cause the orientations of the boundary edges in the solution to differ drastically from the input polygons, which leads to a loss of information about the underlying settlement structure. We explore an alternative method that constructs the subdivision by extending the input building edges, thereby automatically preserving their orientations. To make the approach scalable to large instances without substantially decreasing the solution quality, we propose different methods of reducing the complexity of the subdivision. Our experimental evaluation on real-world data shows that our method is able to aggregate towns containing up to ≈ 10 000 building footprints while preserving input edge orientations much better than state-of-the-art methods.},
    author = {Naumann, Alexander and Bergé, Samuel and Sauer, Jonas and Haunert, Jan-Henrik},
    doi = {10.5194/isprs-annals-XI-4-2026-153-2026},
    journal = {ISPRS Annals of the Photogrammetry, Remote Sensing and Spatial Information Sciences},
    pages = {153--161},
    title = {Building Footprint Aggregation with Preservation of Edge Orientations},
    volume = {XI-4-2026},
    year = {2026}
}

The amount of available geospatial data, particularly different data sets describing the same area, grows continuously. Finding entity correspondences between multiple such datasets is a vital prerequisite for data integration, fusion, and quality assessment. In this work, we focus on polygon datasets, more specifically, building footprints. We compute many-to-many matchings between two input datasets to find correspondences between polygons. Existing research explored heuristic solutions, exact optimization approaches, and machine learning strategies. So far, none of these methods scale well to large datasets while providing a precise problem formulation to measure the quality of a computed matching. We present a fast and versatile algorithm based on a constrained optimization model. Given a partitioning of the datasets into connected subsets, it can solve instances of over 5 million polygons per dataset in under 7 min. Our approach is based on the Jaccard index (intersection over union, IoU) as its central quality measure. However, it is flexible and easily adaptable to different metrics proposed in other works.

doi:10.1016/j.inffus.2025.103360

@article{naumann2025matching,
    abstract = {The amount of available geospatial data, particularly different data sets describing the same area, grows continuously. Finding entity correspondences between multiple such datasets is a vital prerequisite for data integration, fusion, and quality assessment. In this work, we focus on polygon datasets, more specifically, building footprints. We compute many-to-many matchings between two input datasets to find correspondences between polygons. Existing research explored heuristic solutions, exact optimization approaches, and machine learning strategies. So far, none of these methods scale well to large datasets while providing a precise problem formulation to measure the quality of a computed matching. We present a fast and versatile algorithm based on a constrained optimization model. Given a partitioning of the datasets into connected subsets, it can solve instances of over 5 million polygons per dataset in under 7 min. Our approach is based on the Jaccard index (intersection over union, IoU) as its central quality measure. However, it is flexible and easily adaptable to different metrics proposed in other works.},
    author = {Naumann, Alexander and Bonerath, Annika and Haunert, Jan-Henrik},
    doi = {10.1016/j.inffus.2025.103360},
    journal = {Information Fusion},
    pages = {103360},
    publisher = {Elsevier},
    title = {Scalable many-to-many building footprint matching},
    url = {https://www.sciencedirect.com/science/article/pii/S1566253525004336},
    volume = {124},
    year = {2025}
}

Recent developments in consumer-grade panoramic cameras led to new possibilities in creating virtual tours, e.g., through museums or real estate. Most current approaches for the creation of these tours are based on manual generation of navigable links between the images. We consider cases where large numbers of georeferenced images are taken by multiple users and introduce an approach for automatically generating a graph structure that links the images in a reasonable network while sorting out redundant data. Our approach does not expect a trajectory of temporally related points but merely an incoherent point cloud, e.g., from crowdsourcing of many different contributors. We expand our methodology by a visualization approach offering in-image navigation, realized through interactive links pointing towards neighbored images. Our method delivers a virtual tour with adjustable density on and apart from road networks. We compared the output of our algorithm to human-made virtual tour graphs and were able to verify a high similarity, which approves the hypothesis that automatically generated virtual tours can be intuitive for users.

doi:10.1007/s41651-025-00228-1

@article{baltzer2025graph,
    abstract = {Recent developments in consumer-grade panoramic cameras led to new possibilities in creating virtual tours, e.g., through museums or real estate. Most current approaches for the creation of these tours are based on manual generation of navigable links between the images. We consider cases where large numbers of georeferenced images are taken by multiple users and introduce an approach for automatically generating a graph structure that links the images in a reasonable network while sorting out redundant data. Our approach does not expect a trajectory of temporally related points but merely an incoherent point cloud, e.g., from crowdsourcing of many different contributors. We expand our methodology by a visualization approach offering in-image navigation, realized through interactive links pointing towards neighbored images. Our method delivers a virtual tour with adjustable density on and apart from road networks. We compared the output of our algorithm to human-made virtual tour graphs and were able to verify a high similarity, which approves the hypothesis that automatically generated virtual tours can be intuitive for users.},
    author = {Baltzer, Dorian and Naumann, Alexander and Rosenberg, Stephan and Haunert, Jan-Henrik},
    doi = {10.1007/s41651-025-00228-1},
    journal = {Journal of Geovisualization and Spatial Analysis},
    pages = {},
    publisher = {Springer Nature},
    title = {Graph Construction and Interactive Visualization for Virtual Tours Based on Redundant Panoramic Image Collections},
    url = {https://link.springer.com/article/10.1007/s41651-025-00228-1},
    volume = {9},
    year = {2025}
}

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