2026/07/30 by Jan-Henrik Haunert, Joshua Marc Könen, Heiko Röglin +1
Computer Science · #cs.DS
arxiv created 2026/07/30 · arxiv updated 2026/07/31
A problem that occurs in different applications in geographical information science is to generate compact regions from areas on a map. This is important, e.g., in the context of electoral districting to avoid gerrymandering. A common measure for the compactness of a region is the Polsby-Popper score, which measures how close a given region is to a circle based on its area and perimeter. We assume that a polygonal subdivision of the plane is given and study the problem of selecting a subset of the polygonal faces that maximizes the Polsby-Popper score, given by (4πA)/(P2), where A is the area of the selected shape and P is its perimeter. We consider the more general task of maximizing (A)/(Pα) for an arbitrary α>1, which we call the α-circularity problem. We perform the first rigorous study of its complexity and show that it is weakly NP-hard if α∈ (1,2]. Furthermore, for α>1 we present a pseudopolynomial time algorithm for this problem.