Pith. sign in

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.

arxiv 2607.28298 v1 pith:RIR2TR65 submitted 2026-07-30 cs.DS

Finding Regions of Maximum Circularity in Plane Geometric Graphs

classification cs.DS MSC 68Q2568W4090C2705C85
keywords Polsby-Popper scorealpha-circularityplanar graphsPareto optimalitypseudopolynomial algorithmweak NP-hardnesselectoral districtingcompactness
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

Maps are often partitioned into faces, and one wants a single connected region whose shape is as circular as possible. The classical Polsby-Popper score is area over perimeter squared; the paper studies the natural generalization that maximizes area over perimeter to any power alpha greater than 1. The central claim is that this alpha-circularity problem is weakly NP-hard whenever alpha lies between 1 and 2, yet always admits a pseudopolynomial algorithm that works by enumerating Pareto-optimal cycles in a carefully constructed search graph. The algorithm also yields an FPTAS under a mild polynomial-area-ratio assumption and extends to a hardness proof for the related task of partitioning into k districts that maximize the worst-case circularity. A sympathetic reader cares because compactness scores are already used to police gerrymandering and to detect ring roads or tumor margins; knowing the exact complexity and having an implementable exact method changes what practitioners can guarantee.

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.

Watch this falsifier — get emailed when new claim-graph text bears on it.

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

These are editorial extensions of the paper, not claims the author makes directly.

  • 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.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Referee Report

0 major / 5 minor

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)
  1. [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.
  2. [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 α.
  3. [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.
  4. [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.
  5. [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

0 steps flagged

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

0 free parameters · 5 axioms · 0 invented entities

The paper rests on standard planar-graph and isoperimetric facts plus modeling choices that the input is a connected hole-free polygonal subdivision with positive areas and lengths. No physical constants or data-fitted parameters enter the theorems; the only numeric thresholds (Z≥27, N=Z^5, etc.) are proof artifacts inside the reduction.

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].
    Background fact stated in the introduction; not load-bearing for hardness or runtime.
  • 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.
    Section 2 modeling assumptions; Observation 1 and Lemma 4 rely on them.
  • standard math For α>1 an optimum is attained by a single simple cycle (no holes, no disconnected components).
    Lemma 2 + Observation 3; proved from strict convexity/superadditivity of x^α.
  • standard math Park–Phillips search-graph weight lemma: for every simple cycle C, |w(C)|=A(C) and ℓ'(C)=ℓ(C).
    Lemma 5; paper supplies a full proof in appendix B.1 because the original omitted it.
  • standard math PARTITION is weakly NP-complete.
    Classical fact used as the source problem in Section 5.

pith-pipeline@v1.2.0-daily-grok45 · 36192 in / 2658 out tokens · 60328 ms · 2026-07-31T11:54:26.528622+00:00 · methodology

0 comments
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.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

62 extracted references · 9 canonical work pages

  1. [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. [2]

    and Kim, Chul E

    Ibarra, Oscar H. and Kim, Chul E. , title =. 1975 , issue_date =. doi:10.1145/321906.321909 , journal =

  3. [3]

    Algorithmica , month =

    Gu, Qian-Ping and Tamaki, Hisao , title =. Algorithmica , month =. 2012 , issue_date =. doi:10.1007/s00453-012-9627-5 , abstract =

  4. [4]

    and Thomas, R

    Seymour, Paul D. and Thomas, R. , title =. 1994 , journal =

  5. [5]

    Hicks , title=

    Illya V. Hicks , title=. INFORMS Journal on Computing , year=2005, volume=. doi:10.1287/ijoc.1040.0075 , abstract=

  6. [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 =

  7. [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 =

  8. [8]

    CoRR , volume =

    Carolin Albrecht and Frank Gurski and Jochen Rethmann and Eda Yilmaz , title =. CoRR , volume =. 2016 , url =. 1611.07724 , timestamp =

  9. [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 =

  10. [10]

    2012 , publisher=

    Parameterized complexity , author=. 2012 , publisher=

  11. [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 =

  12. [12]

    Annals of Operations Research , volume=

    On spanning tree problems with multiple objectives , author=. Annals of Operations Research , volume=. 1994 , publisher=

  13. [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. [14]

    Graph minors. II. Algorithmic aspects of tree-width , author=. Journal of algorithms , volume=. 1986 , publisher=

  15. [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. [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=

  17. [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. [18]

    On the cardinality of the

    Matthias M. On the cardinality of the. Ann. Oper. Res. , volume =. 2006 , url =. doi:10.1007/s10479-006-0072-1 , timestamp =

  19. [19]

    2005 , url =

    Matthias Ehrgott , title =. 2005 , url =. doi:10.1007/3-540-27659-9 , isbn =

  20. [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. [21]

    The smoothed number of

    Ren. The smoothed number of. Mathematical Programming , doi =

  22. [22]

    1985 , volume =

    Shortest paths in networks with vector weights , journal =. 1985 , volume =

  23. [23]

    Nemhauser and Zev Ullmann , title =

    George L. Nemhauser and Zev Ullmann , title =. Management Science , volume =

  24. [24]

    Investigacao Operacional , year =

    Matthias Ehrgott , title =. Investigacao Operacional , year =

  25. [25]

    Computers

    Adli Mustafa and Mark Goh , title =. Computers. 1998 , pages =

  26. [26]

    Multiple Criteria Decision Making: Theory and Applications , pages =

    Pierre Hansen , title =. Multiple Criteria Decision Making: Theory and Applications , pages =. 1980 , volume =

  27. [27]

    Anders J. V. Skriver and Kim Allan Andersen , title =. Computers. 2000 , pages =

  28. [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. [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=

  30. [30]

    International Transactions in Operational Research , volume=

    Approximation algorithms for combinatorial multicriteria optimization problems , author=. International Transactions in Operational Research , volume=. 2000 , publisher=

  31. [31]

    Algorithmica , volume=

    Approximation algorithms for multi-criteria traveling salesman problems , author=. Algorithmica , volume=. 2009 , publisher=

  32. [32]

    Dey , title =

    Tamal K. Dey , title =. Proc. of the 38th Annual IEEE Symposium on Foundations of Computer Science (

  33. [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. [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. [35]

    2012 , url =

    Ankur Moitra and Ryan O'Donnell , title =. 2012 , url =. doi:10.1137/110851833 , timestamp =

  36. [36]

    and Phillips, Cynthia A

    Park, James K. and Phillips, Cynthia A. , title =. 1993 , isbn =. doi:10.1145/167088.167284 , booktitle =

  37. [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. [38]

    CoRR , volume =

    Viresh Patel , title =. CoRR , volume =. 2010 , url =. 1004.4484 , timestamp =

  39. [39]

    Arora, Sanjeev and Rao, Satish and Vazirani, Umesh , title =. J. ACM , month = apr, articleno =. 2009 , issue_date =. doi:10.1145/1502793.1502794 , abstract =

  40. [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. [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. [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 =

  43. [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 =

  44. [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 =

  45. [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. [46]

    1999 , isbn =

    Rao, Satish , title =. 1999 , isbn =. doi:10.1145/304893.304983 , booktitle =

  47. [47]

    CoRR , volume =

    Sergio Cabello , title =. CoRR , volume =. 2017 , url =. 1702.07815 , timestamp =

  48. [48]

    Pietro Belotti and Austin Buchanan and Soraya Ezazipour , title =. Oper. Res. , volume =. 2025 , url =

  49. [49]

    Yale Law & Policy Review , year=

    The Third Criterion: Compactness as a Procedural Safeguard Against Partisan Gerrymandering , author=. Yale Law & Policy Review , year=

  50. [50]

    GeoInformatica , volume =

    Takeshi Shirabe , title =. GeoInformatica , volume =. 2005 , doi =

  51. [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 =

  52. [52]

    Maceachren , title =

    Alan M. Maceachren , title =. Geografiska Annaler: Series B, Human Geography , volume =. 1985 , doi =

  53. [53]

    Operations Research , volume =

    Hamidreza Validi and Austin Buchanan and Eugene Lykhovyd , title =. Operations Research , volume =. 2022 , doi =

  54. [54]

    1991 , author =

    The Third Criterion: Compactness as a Procedural Safeguard Against Partisan Gerrymandering , journal =. 1991 , author =

  55. [55]

    and Church, Richard L

    Cova, Thomas J. and Church, Richard L. , title =. Geographical Analysis , volume =. doi:https://doi.org/10.1111/j.1538-4632.2000.tb00430.x , year =

  56. [56]

    Political Analysis , author =

    Gerrymandering and Compactness: Implementation Flexibility and Abuse , volume =. Political Analysis , author =. 2021 , pages =. doi:10.1017/pan.2020.36 , Number =

  57. [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 =

  58. [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 =

  59. [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=

  60. [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. [61]

    2026 , eprint=

    The Art of Being Difficult: Combining Human and AI Strengths to Find Adversarial Instances for Heuristics , author=. 2026 , eprint=

  62. [62]

    Recombination: A family of

    Daryl DeFord and Moon Duchin and Justin Solomon , year=. Recombination: A family of. 1911.05725 , archivePrefix=