REVIEW 5 minor 62 references
Selecting faces to maximize area over perimeter to the alpha is weakly NP-hard for alpha in (1,2], yet solvable in pseudopolynomial time for every alpha greater than 1.
Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →
T0 review · grok-4.5
2026-07-31 11:54 UTC pith:RIR2TR65
load-bearing objection Solid first complexity treatment of Polsby-Popper optimization: weak NP-hardness for α∈(1,2] plus a correct pseudopolynomial Pareto-cycle algorithm that fixes intermediate weight bounds.
Finding Regions of Maximum Circularity in Plane Geometric Graphs
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
Core claim
For every alpha greater than 1 an optimal subset of faces maximizing A/P^alpha can be found in time O(n^2 m p_max), where p_max is the size of the largest intermediate Pareto set; under integer areas or lengths this becomes O(n^3 m A_total) or O(n^2 m P_total). For alpha in (1,2] the same problem is weakly NP-hard by reduction from Partition.
What carries the argument
The directed search graph built from a spanning tree of the dual: every simple cycle's enclosed area appears as the algebraic sum of edge weights, so bicriteria Bellman-Ford can list all Pareto-optimal (length, area) pairs and the best alpha-ratio among them is optimal.
Load-bearing premise
The hardness proof needs a concrete geometric sizing (side length Z^5, rectangle height Z^2, and a derived constant c) so that after clipping no competing selection of rectangles can beat the score achieved exactly at half the total area; if those polynomial relations fail for some alpha or Z the reduction collapses.
What would settle it
Implement the Pareto-cycle algorithm and the Partition reduction for a family of small integer instances with known optimal partitions; if either the reported circularity score is not achieved precisely when a perfect half-sum exists, or a better non-partition selection appears, the claimed equivalence is false.
If this is right
- Exact maximum-Polsby-Popper regions can be computed on moderate-size maps whenever areas or edge lengths are integers of moderate magnitude.
- The same dynamic program immediately yields the full Pareto front of area-versus-perimeter trade-offs, not merely the single best ratio.
- The k-districting variant that maximizes the worst district circularity is also weakly NP-hard for every fixed k greater than or equal to 2 and alpha in (1,2].
- Under a polynomial bound on total-to-minimum area an FPTAS exists, giving a practical approximation route when exact integers are unavailable.
Where Pith is reading between the lines
- Because real cartographic instances empirically produce tiny Pareto sets, the algorithm is likely to finish far faster than the worst-case pseudopolynomial bound suggests, making it usable inside interactive districting tools.
- The same search-graph technique should apply verbatim to any other scale-invariant compactness score that is a strictly decreasing function of perimeter for fixed area.
- Extending the hardness side beyond alpha=2 remains open; a matching hardness proof for larger alpha would complete the complexity map.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper studies the α-circularity problem: given a plane polygonal subdivision, select a subset of faces maximizing A/P^α for fixed α>1 (recovering the Polsby-Popper score at α=2). The authors prove that an optimum is always realized by a simple cycle (Observation 3, Lemma 2), adapt the Park–Phillips search-graph construction, and compute the Pareto front of length-versus-enclosed-area paths by a bicriteria Bellman–Ford procedure (Algorithm 1). This yields a pseudopolynomial algorithm of time O(n² m p_max), hence O(n³ m A_total) or O(n² m P_total) under integer areas or lengths (Theorem 8, Corollary 9). For α∈(1,2] they give a careful weak-NP-hardness reduction from PARTITION via an almost-square with attached rectangles whose side lengths are polynomially sized in the PARTITION total Z (Section 5, Lemmata 12–16, Theorem 17). The same construction is extended to show weak NP-hardness of maximizing the minimum α-circularity over a partition into exactly k districts (Appendix G). Experiments on Rhein-Ruhr subsets illustrate that p_max stays tiny in practice.
Significance. This is the first rigorous complexity-theoretic treatment of optimizing the classical Polsby-Popper compactness score (and its natural one-parameter generalization) over face subsets of a plane map. The algorithmic contribution is clean: it correctly repairs the intermediate-weight bound of the classic planar quotient-cut algorithm (Section F) and replaces the expanded-graph Dijkstra with explicit Pareto-set maintenance, which is both theoretically justified (Lemmata 5–7) and practically far more stable under high-precision weights (Section E). The hardness proof is fully explicit, with concrete polynomial sizing and derivative arguments that leave comfortable slack. Together the results give a complete weak-NP-completeness picture for α∈(1,2] and a usable exact algorithm for all α>1, which is of genuine interest to computational geometry, GIS, and electoral-districting communities.
minor comments (5)
- [Section 5 / Theorem 17] The open case α>2 is stated clearly but never discussed beyond the hardness threshold. A short remark on why the PARTITION reduction fails for α>2 (or a pointer to the place where the second-derivative sign flips) would help the reader.
- [Figure 1] Figure 1 captions and the surrounding text use α=3,2,1.1; it would be useful to report the numerical c_α values attained by the three highlighted regions so the reader can see the quantitative effect of α.
- [Section E] In the experimental section the precise definition of an “operation” for Algorithm 1 (sum of Pareto-set sizes at each merge) is given only in the appendix-style text; moving a one-sentence definition into the main experimental narrative would improve reproducibility.
- [front matter / Section 5] Typographical: “envel⌢pe/h⌢me” artefacts appear in the author block; several “¯li” vs “li” renderings are inconsistent in the hardness construction; “Atotal/Amin≤f(m)” should be typeset with a proper fraction.
- [Section 4] The FPTAS (Theorem 11) assumes Atotal/Amin is polynomially bounded. A brief note that this is automatic for integer areas of bit length poly(log n) would clarify the practical scope.
Circularity Check
No significant circularity: self-contained algorithm and PARTITION reduction
full rationale
This is a standard theoretical algorithms paper. The α-circularity objective is stated explicitly and optimized directly via Pareto-optimal cycles in a search graph adapted from Park–Phillips; correctness rests on proved lemmas (superadditivity for α>1 ruling out disconnected/non-simple solutions, bicriteria Bellman–Ford, and the intermediate-weight bound fix in Section F), not on fitted parameters or self-referential definitions. Hardness is a many-one reduction from PARTITION with an explicit geometric construction (N=Z^5, b=Z^2, c chosen so c_α(x) peaks uniquely at x=Z/2) and derivative/comparison arguments (Lemmata 12–16). Citations to quotient-cut and smoothed-analysis work are used as tools, not as load-bearing uniqueness claims that force the result. No prediction-that-is-a-fit, no self-definitional loop, and no renaming of a known empirical pattern as a derivation.
Axiom & Free-Parameter Ledger
axioms (5)
- standard math Isoperimetric inequality: 4πA ≤ P² with equality iff the region is a circle; used only to motivate the score range [0,1].
- domain assumption Input is a connected Euclidean plane graph whose faces are the candidate polygons, with positive edge lengths and positive face areas, and the subdivision has no holes.
- standard math For α>1 an optimum is attained by a single simple cycle (no holes, no disconnected components).
- standard math Park–Phillips search-graph weight lemma: for every simple cycle C, |w(C)|=A(C) and ℓ'(C)=ℓ(C).
- standard math PARTITION is weakly NP-complete.
read the original abstract
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 $\frac{4\pi A}{P^2}$, where $A$ is the area of the selected shape and $P$ is its perimeter. We consider the more general task of maximizing $\frac{A}{P^\alpha}$ for an arbitrary $\alpha>1$, which we call the $\alpha$-circularity problem. We perform the first rigorous study of its complexity and show that it is weakly NP-hard if $\alpha \in (1,2]$. Furthermore, for $\alpha>1$ we present a pseudopolynomial time algorithm for this problem.
Reference graph
Works this paper leans on
-
[1]
11th International Conference on Geographic Information Science (GIScience 2021) - Part II , pages =
Rottmann, Peter and Driemel, Anne and Haverkort, Herman and R\". 11th International Conference on Geographic Information Science (GIScience 2021) - Part II , pages =. 2021 , volume =. doi:10.4230/LIPIcs.GIScience.2021.II.6 , annote =
-
[2]
Ibarra, Oscar H. and Kim, Chul E. , title =. 1975 , issue_date =. doi:10.1145/321906.321909 , journal =
arXiv 1975
-
[3]
Gu, Qian-Ping and Tamaki, Hisao , title =. Algorithmica , month =. 2012 , issue_date =. doi:10.1007/s00453-012-9627-5 , abstract =
-
[4]
and Thomas, R
Seymour, Paul D. and Thomas, R. , title =. 1994 , journal =
1994
-
[5]
Illya V. Hicks , title=. INFORMS Journal on Computing , year=2005, volume=. doi:10.1287/ijoc.1040.0075 , abstract=
arXiv 2005
-
[6]
and Kowalik, Lukasz and Lokshtanov, Daniel and Marx, Daniel and Pilipczuk, Marcin and Pilipczuk, Michal and Saurabh, Saket , title =
Cygan, Marek and Fomin, Fedor V. and Kowalik, Lukasz and Lokshtanov, Daniel and Marx, Daniel and Pilipczuk, Marcin and Pilipczuk, Michal and Saurabh, Saket , title =. 2015 , isbn =
2015
-
[7]
Jones and Geraint L1
Christopher B. Jones and Geraint L1. Bundy and Mark J. Ware , title =. Cartography and Geographic Information Systems , volume =. 1995 , publisher =
1995
-
[8]
Carolin Albrecht and Frank Gurski and Jochen Rethmann and Eda Yilmaz , title =. CoRR , volume =. 2016 , url =. 1611.07724 , timestamp =
Pith/arXiv arXiv 2016
-
[9]
Fellows and Serge Gaspers and Frances A
Michael R. Fellows and Serge Gaspers and Frances A. Rosamond , title =. CoRR , volume =. 2010 , url =. 1007.2021 , timestamp =
Pith/arXiv arXiv 2010
-
[10]
2012 , publisher=
Parameterized complexity , author=. 2012 , publisher=
2012
-
[11]
Polynomial Kernels for Weighted Problems , journal =
Michael Etscheid and Stefan Kratsch and Matthias Mnich and Heiko R. Polynomial Kernels for Weighted Problems , journal =. 2015 , url =. 1507.03439 , timestamp =
Pith/arXiv arXiv 2015
-
[12]
Annals of Operations Research , volume=
On spanning tree problems with multiple objectives , author=. Annals of Operations Research , volume=. 1994 , publisher=
1994
-
[13]
Kung, H. T. and Luccio, F. and Preparata, F. P. , year =. On Finding the Maxima of a Set of Vectors , pages =. Journal of the ACM , doi =
-
[14]
Graph minors. II. Algorithmic aspects of tree-width , author=. Journal of algorithms , volume=. 1986 , publisher=
1986
-
[15]
Probability and Mathematical Statistics , volume=
Improved bounds on Bell numbers and on moments of sums of random variables , author=. Probability and Mathematical Statistics , volume=
-
[16]
SIAM Journal on Algebraic Discrete Methods , volume=
Complexity of finding embeddings in ak-tree , author=. SIAM Journal on Algebraic Discrete Methods , volume=. 1987 , publisher=
1987
-
[17]
Proceedings of the twenty-fifth annual ACM symposium on Theory of computing , pages=
A linear time algorithm for finding tree-decompositions of small treewidth , author=. Proceedings of the twenty-fifth annual ACM symposium on Theory of computing , pages=
-
[18]
Matthias M. On the cardinality of the. Ann. Oper. Res. , volume =. 2006 , url =. doi:10.1007/s10479-006-0072-1 , timestamp =
-
[19]
Matthias Ehrgott , title =. 2005 , url =. doi:10.1007/3-540-27659-9 , isbn =
-
[20]
Improved Smoothed Analysis of Multiobjective Optimization , journal =
Tobias Brunsch and Heiko R. Improved Smoothed Analysis of Multiobjective Optimization , journal =. 2015 , url =. doi:10.1145/2699445 , timestamp =
-
[21]
The smoothed number of
Ren. The smoothed number of. Mathematical Programming , doi =
-
[22]
1985 , volume =
Shortest paths in networks with vector weights , journal =. 1985 , volume =
1985
-
[23]
Nemhauser and Zev Ullmann , title =
George L. Nemhauser and Zev Ullmann , title =. Management Science , volume =
-
[24]
Investigacao Operacional , year =
Matthias Ehrgott , title =. Investigacao Operacional , year =
-
[25]
Computers
Adli Mustafa and Mark Goh , title =. Computers. 1998 , pages =
1998
-
[26]
Multiple Criteria Decision Making: Theory and Applications , pages =
Pierre Hansen , title =. Multiple Criteria Decision Making: Theory and Applications , pages =. 1980 , volume =
1980
-
[27]
Anders J. V. Skriver and Kim Allan Andersen , title =. Computers. 2000 , pages =
2000
-
[28]
Output-sensitive Complexity of Multiobjective Combinatorial Optimization with an Application to the Multiobjective Shortest Path Problem , school =
Fritz B. Output-sensitive Complexity of Multiobjective Combinatorial Optimization with an Application to the Multiobjective Shortest Path Problem , school =
-
[29]
Proceedings 41st annual symposium on foundations of computer science , pages=
On the approximability of trade-offs and optimal access of web sources , author=. Proceedings 41st annual symposium on foundations of computer science , pages=. 2000 , organization=
2000
-
[30]
International Transactions in Operational Research , volume=
Approximation algorithms for combinatorial multicriteria optimization problems , author=. International Transactions in Operational Research , volume=. 2000 , publisher=
2000
-
[31]
Algorithmica , volume=
Approximation algorithms for multi-criteria traveling salesman problems , author=. Algorithmica , volume=. 2009 , publisher=
2009
-
[32]
Dey , title =
Tamal K. Dey , title =. Proc. of the 38th Annual IEEE Symposium on Foundations of Computer Science (
-
[33]
Agarwal and David Eppstein and Leonidas J
Pankaj K. Agarwal and David Eppstein and Leonidas J. Guibas and Monika Rauch Henzinger , title =. Proc. of the 39th Annual IEEE Symposium on Foundations of Computer Science (
-
[34]
Smoothed Analysis of Multiobjective Optimization , booktitle =
Heiko R. Smoothed Analysis of Multiobjective Optimization , booktitle =. 2009 , url =. doi:10.1109/FOCS.2009.21 , timestamp =
-
[35]
Ankur Moitra and Ryan O'Donnell , title =. 2012 , url =. doi:10.1137/110851833 , timestamp =
-
[36]
Park, James K. and Phillips, Cynthia A. , title =. 1993 , isbn =. doi:10.1145/167088.167284 , booktitle =
arXiv 1993
-
[37]
The quadratic shortest path problem: complexity, approximability, and solution methods , journal =
Borzou Rostami and André Chassein and Michael Hopf and Davide Frey and Christoph Buchheim and Federico Malucelli and Marc Goerigk , keywords =. The quadratic shortest path problem: complexity, approximability, and solution methods , journal =. 2018 , issn =. doi:https://doi.org/10.1016/j.ejor.2018.01.054 , url =
-
[38]
Viresh Patel , title =. CoRR , volume =. 2010 , url =. 1004.4484 , timestamp =
Pith/arXiv arXiv 2010
-
[39]
Arora, Sanjeev and Rao, Satish and Vazirani, Umesh , title =. J. ACM , month = apr, articleno =. 2009 , issue_date =. doi:10.1145/1502793.1502794 , abstract =
arXiv 2009
-
[40]
Proceedings of the 2017 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , chapter =
Moses Charikar and Vaggos Chatziafratis , title =. Proceedings of the 2017 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , chapter =. doi:10.1137/1.9781611974782.53 , URL =. https://epubs.siam.org/doi/pdf/10.1137/1.9781611974782.53 , abstract =
-
[41]
Matula and Farhad Shahrokhi , abstract =
David W. Matula and Farhad Shahrokhi , abstract =. Sparsest cuts and bottlenecks in graphs , journal =. 1990 , issn =. doi:https://doi.org/10.1016/0166-218X(90)90133-W , url =
-
[42]
Proceedings of the Forty-Fifth Annual ACM Symposium on Theory of Computing , pages =
Gupta, Anupam and Talwar, Kunal and Witmer, David , title =. Proceedings of the Forty-Fifth Annual ACM Symposium on Theory of Computing , pages =. 2013 , isbn =. doi:10.1145/2488608.2488644 , abstract =
arXiv 2013
-
[43]
Proceedings of the Thirty-Seventh Annual ACM Symposium on Theory of Computing , pages =
Euclidean distortion and the Sparsest Cut , author =. Proceedings of the Thirty-Seventh Annual ACM Symposium on Theory of Computing , pages =. 2005 , isbn =. doi:10.1145/1060590.1060673 , abstract =
arXiv 2005
-
[44]
New Hardness Results for Planar Graph Problems in
Amir Abboud and Vincent Cohen. New Hardness Results for Planar Graph Problems in. CoRR , volume =. 2020 , url =. 2007.02377 , timestamp =
Pith/arXiv arXiv 2020
-
[45]
Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing , year=
A quasipolynomial (2 + )-approximation for planar sparsest cut , author=. Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing , year=
-
[46]
Rao, Satish , title =. 1999 , isbn =. doi:10.1145/304893.304983 , booktitle =
arXiv 1999
-
[47]
Sergio Cabello , title =. CoRR , volume =. 2017 , url =. 1702.07815 , timestamp =
Pith/arXiv arXiv 2017
-
[48]
Pietro Belotti and Austin Buchanan and Soraya Ezazipour , title =. Oper. Res. , volume =. 2025 , url =
2025
-
[49]
Yale Law & Policy Review , year=
The Third Criterion: Compactness as a Procedural Safeguard Against Partisan Gerrymandering , author=. Yale Law & Policy Review , year=
-
[50]
GeoInformatica , volume =
Takeshi Shirabe , title =. GeoInformatica , volume =. 2005 , doi =
2005
-
[51]
Pattern Recognition in Road Networks on the Example of Circular Road Detection , booktitle =
Heinzle, Frauke and Anders, Karl-Heinrich and Sester, Monika , editor =. Pattern Recognition in Road Networks on the Example of Circular Road Detection , booktitle =. 2006 , pages =
2006
-
[52]
Maceachren , title =
Alan M. Maceachren , title =. Geografiska Annaler: Series B, Human Geography , volume =. 1985 , doi =
1985
-
[53]
Operations Research , volume =
Hamidreza Validi and Austin Buchanan and Eugene Lykhovyd , title =. Operations Research , volume =. 2022 , doi =
2022
-
[54]
1991 , author =
The Third Criterion: Compactness as a Procedural Safeguard Against Partisan Gerrymandering , journal =. 1991 , author =
1991
-
[55]
Cova, Thomas J. and Church, Richard L. , title =. Geographical Analysis , volume =. doi:https://doi.org/10.1111/j.1538-4632.2000.tb00430.x , year =
arXiv 2000
-
[56]
Gerrymandering and Compactness: Implementation Flexibility and Abuse , volume =. Political Analysis , author =. 2021 , pages =. doi:10.1017/pan.2020.36 , Number =
-
[57]
Proceedings of the 21st International Conference on Autonomous Agents and Multiagent Systems , series =
Borodin, Allan and Lev, Omer and Shah, Nisarg and Strangway, Tyrone , title =. Proceedings of the 21st International Conference on Autonomous Agents and Multiagent Systems , series =. 2022 , publisher =
2022
-
[58]
Cervas and Bernard Grofman , keywords =
Jonathan R. Cervas and Bernard Grofman , keywords =. Tools for identifying partisan gerrymandering with an application to congressional districting in. Political Geography , volume =. 2020 , issn =. doi:https://doi.org/10.1016/j.polgeo.2019.102069 , url =
arXiv 2020
-
[59]
Journal of Optimization Theory and Applications , volume=
Shortest paths in networks with vector weights , author=. Journal of Optimization Theory and Applications , volume=. 1985 , publisher=
1985
-
[60]
and Rupp, Robin and Mueller, Sarina K
Csűry, Tamás Dániel and Csűry, Anna Zsófia and Balk, Matthias and Kist, Andreas M. and Rupp, Robin and Mueller, Sarina K. and Sievert, Matti and Iro, Heinrich and Eckstein, Markus and Gostian, Antoniu-Oreste , title =. Cancer Medicine , volume =. doi:https://doi.org/10.1002/cam4.6824 , year =
-
[61]
2026 , eprint=
The Art of Being Difficult: Combining Human and AI Strengths to Find Adversarial Instances for Heuristics , author=. 2026 , eprint=
2026
-
[62]
Daryl DeFord and Moon Duchin and Justin Solomon , year=. Recombination: A family of. 1911.05725 , archivePrefix=
Pith/arXiv arXiv 1911
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.