2026-08-25T14:43:39Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:27147 2026-08-25T13:18:15Z ddc:004 open_access

Bicriteria Polygon Aggregation with Arbitrary Shapes Blank, Lotte Eppstein, David Haunert, Jan-Henrik Haverkort, Herman Kolbe, Benedikt Mayer, Philip Mutzel, Petra Naumann, Alexander Sauer, Jonas polygon aggregation fencing minimum-perimeter clustering map generalization urban analytics 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Lotte Blank and David Eppstein and Jan-Henrik Haunert and Herman Haverkort and Benedikt Kolbe and Philip Mayer and Petra Mutzel and Alexander Naumann and Jonas Sauer 2026 Is Part Of LIPIcs, Volume 388, 34th Annual European Symposium on Algorithms (ESA 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2026.11 urn:nbn:de:0030-drops-271472 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2026.11 eng https://creativecommons.org/licenses/by/4.0/legalcode