pith. machine review for the scientific record. sign in

arxiv: 2604.26749 · v2 · submitted 2026-04-29 · 💻 cs.CG

Recognition: no theorem link

The Nesting Bird Box Problem is ER-complete: Sharp Hardness Results for the Hidden Set Problem

Johanna Ockenfels, Lucas Meijer, Milo\v{s} Stojakovi\'c, Till Miltzow

Authors on Pith no claims yet

Pith reviewed 2026-05-14 21:24 UTC · model grok-4.3

classification 💻 cs.CG
keywords Nesting Bird Box ProblemER-completenessHidden Set ProblemVisibility ConstraintsPolygonal Domains with HolesArt Gallery ProblemComputational Geometry
0
0 comments X

The pith

The Nesting Bird Box problem of placing k mutually invisible points in a polygonal domain is ER-complete.

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

The paper proves that deciding whether a polygonal domain contains k points with no two mutually visible is complete for the complexity class ER. ER-complete problems are polynomial-time equivalent to determining whether a system of polynomial equations with integer coefficients has a real solution. The result applies to polygonal domains that may contain holes, and the visibility definition requires that the open segment between two points lies entirely inside the domain and avoids all vertices. A sympathetic reader cares because this places a natural geometric problem at the same hardness level as real-algebraic decision problems, which sit between NP and PSPACE. The proof is notably shorter than the corresponding argument for the Art Gallery problem because it permits holes and uses recently developed reduction tools.

Core claim

The central claim is that the Nesting Bird Box problem is ER-complete. Given a polygonal domain P (possibly with holes) and integer k, the task is to decide whether there exists a set B of k points inside P such that no two points in B see each other. Two points a and b see each other when the open segment ab intersects neither the exterior of P nor any vertex of P. The proof proceeds by polynomial-time reduction from known ER-complete problems, constructing domains with holes whose visibility constraints encode exactly the solution set of the original polynomial system.

What carries the argument

A reduction from ER-complete polynomial satisfiability to the hidden-set decision problem that encodes real solutions as sets of mutually invisible points inside a polygonal domain with holes.

If this is right

  • The hidden-set problem remains ER-complete even when the input is restricted to polygonal domains with holes.
  • Exact computation of the maximum number of mutually invisible points is ER-hard.
  • The same reduction technique yields ER-completeness for the decision version of the problem for every fixed k at least some constant.
  • No algorithm running in time polynomial in the input size and the bit length of the coordinates can solve the problem unless the existential theory of the reals itself lies in P.

Where Pith is reading between the lines

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

  • The same style of reduction may extend to other visibility-based selection problems such as maximum independent sets in visibility graphs of polygons with holes.
  • Allowing holes appears to simplify the construction of exact encodings for real-algebraic constraints compared with simple polygons.
  • The result suggests that approximation versions of the hidden-set problem may still be NP-hard even when the exact version sits in ER.

Load-bearing premise

The reduction from known ER-complete problems constructs polygonal domains with holes whose visibility constraints exactly encode the original polynomial system without introducing extraneous solutions or visibility artifacts.

What would settle it

An explicit polynomial system that has a real solution together with the corresponding constructed polygon instance that admits no valid set of k mutually invisible points (or vice versa) would show the reduction fails.

Figures

Figures reproduced from arXiv: 2604.26749 by Johanna Ockenfels, Lucas Meijer, Milo\v{s} Stojakovi\'c, Till Miltzow.

Figure 1
Figure 1. Figure 1: An overview of our construction. The variable gadgets at the bottom encode variables. The view at source ↗
Figure 2
Figure 2. Figure 2: Left: The polygon is covered with two fully visible regions. Each region can contain at most one view at source ↗
Figure 3
Figure 3. Figure 3: A blocker. Note that it can be made arbitrarily thin. view at source ↗
Figure 4
Figure 4. Figure 4: The construction of the triangular pockets that contain spectators at their convex vertex. Here, view at source ↗
Figure 5
Figure 5. Figure 5: Ensuring all of etop and ebottom are covered. The spectator at p1 covers the first edge, the spectator at p2 the second edge, etc. This construction can be made arbitrarily thin. p3 p4 p1 p2 view at source ↗
Figure 6
Figure 6. Figure 6: The basic construction of the variable gadget with four spectators and one birdhouse segment. For view at source ↗
Figure 7
Figure 7. Figure 7: The ≤-scaling gadget is a nook in the upper part of the polygon. It consists of two pivot points and a critical segment. The gadget is connected to two birdhouse segments. rotation or be made longer or shorter, depending on the positions of the triangular pockets. The threshold for this gadget equals 5. We interpret the value of the left most point of the birdhouse segment as −1, the point of the right mos… view at source ↗
Figure 7
Figure 7. Figure 7: Likewise, if the region between the pivot points is a hole in the polygon, we have a view at source ↗
Figure 8
Figure 8. Figure 8: Construction of the ≥-gadget. The black disks represent the position of the spectators, which we denote by p1, p2, . . . , p6 in counterclockwise order. Calculation. We will now prove that if the rays from x and y through p and q intersect on the critical segment, then x and y encode the same value. To this end, we say xi is the point at which x would encode −1 ≤ i ≤ 1. We define yi analogously view at source ↗
Figure 9
Figure 9. Figure 9: If the birdhouses are at a good position, we can place an additional birdhouse inside the gadget. view at source ↗
Figure 10
Figure 10. Figure 10: The figure contains the points and length to show that the scaling gadget enforces a linear view at source ↗
Figure 11
Figure 11. Figure 11: The ≥ addition gadget. The reverse gadget is the exact mirror image. The black disks represent the position of the spectators. First, we describe a gadget enforcing x + y ≥ z. We call this the ≥-addition gadget. Thereafter, we describe the very similar ≤-addition gadget enforcing x + y ≤ z. Description of the ≥-Addition Gadget. We want to point out that our addition gadget follows the ideas of Abrahamsen,… view at source ↗
Figure 12
Figure 12. Figure 12: Illustration of different lengths in the addition gadget. view at source ↗
Figure 13
Figure 13. Figure 13: The curved gadget with the visibility regions of the spectators in the gadget. Note that the two view at source ↗
Figure 14
Figure 14. Figure 14: Schematic drawing for the calculation of the curvedness. view at source ↗
read the original abstract

In the (Nesting) Bird Box Problem we are given a polygonal domain P and a number k and we want to know if there is a set B of k points inside P such that no two points in B can see each other. The underlying idea is that each point represents a birdhouse and many birds only use a birdhouse if there is no other occupied birdhouse in its vicinity. We say two points a,b see each other if the open segment ab intersects neither the exterior of P nor any vertex of P. We show that the Nesting Bird Box problem is ER-complete. The complexity class ER can be defined by the set of problems that are polynomial time equivalent to finding a solution to the equation $p(x) = 0$, with $x\in R^n$ and $p\in $Z[X_1,...,X_n]$. The proof builds on the techniques developed in the original ER-completeness proof of the Art Gallery problem. However our proof is significantly shorter for two reasons. First, we can use recently developed tools that were not available at the time. Second, we consider polygonal domains with holes instead of simple polygons.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The paper proves that the Nesting Bird Box problem—given a polygonal domain P (with holes) and integer k, decide if there exists a hidden set of k mutually invisible points inside P—is ER-complete. Visibility is defined via open segments that intersect neither the exterior of P nor any vertex. The proof is a many-one reduction from known ER-complete problems (e.g., deciding real solutions to polynomial systems p(x)=0), and is claimed to be significantly shorter than the prior ER-completeness proof for the Art Gallery problem by exploiting holes and recently developed tools.

Significance. If the reduction holds, the result supplies sharp ER-completeness for the hidden-set problem in domains with holes, extending the line of work on visibility problems begun with the Art Gallery ER-completeness result. The use of holes and modern tools to shorten the argument is a technical contribution; the paper also supplies a clean, falsifiable geometric encoding of algebraic constraints.

major comments (2)
  1. [§3] §3 (Reduction from ER-complete polynomial systems): the central claim requires that the hole-based gadgets enforce exactly the algebraic constraints without extraneous hidden-set solutions. The construction must be shown to block all unintended lines of sight that could place mutually invisible points failing to satisfy p(x)=0; the manuscript should supply an explicit case analysis or invariant (e.g., for each gadget type) proving the “only if” direction.
  2. [§3.2] §3.2 (Gadget definitions): because holes are used (unlike the simple-polygon Art Gallery reduction), any hole geometry that permits a line of sight “around” a constraint gadget would falsify the equivalence. The paper must verify that the chosen hole placements and vertex placements eliminate such artifacts for every variable and equation gadget.
minor comments (2)
  1. [Abstract] Abstract and §1: the visibility definition (“open segment ab intersects neither the exterior of P nor any vertex”) should explicitly state whether the segment may touch the boundary of P at non-vertex points; this affects the precise notion of “hidden.”
  2. [§4] §4 (Conclusion): the statement that the proof is “significantly shorter” would be strengthened by a brief comparison table or paragraph quantifying the number of gadgets or lemmas versus the prior Art Gallery proof.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and constructive feedback. The comments highlight the need for more explicit verification of the gadget correctness in the reduction. We address each point below and will revise the manuscript to strengthen the proof of equivalence.

read point-by-point responses

  1. Referee: [§3] §3 (Reduction from ER-complete polynomial systems): the central claim requires that the hole-based gadgets enforce exactly the algebraic constraints without extraneous hidden-set solutions. The construction must be shown to block all unintended lines of sight that could place mutually invisible points failing to satisfy p(x)=0; the manuscript should supply an explicit case analysis or invariant (e.g., for each gadget type) proving the “only if” direction.

    Authors: We agree that an explicit case analysis strengthens the 'only if' direction. The holes are placed to intersect any potential bypassing segment, but the manuscript's current argument is somewhat implicit. In the revision we will add a new subsection to §3 containing an invariant for each gadget type (variable, equation, and auxiliary), proving that any hidden set of size k must encode a real solution to p(x)=0. The argument proceeds by contradiction: any extraneous mutually invisible point would require a visibility segment crossing a hole boundary or vertex, which is forbidden by definition. revision: yes

  2. Referee: [§3.2] §3.2 (Gadget definitions): because holes are used (unlike the simple-polygon Art Gallery reduction), any hole geometry that permits a line of sight “around” a constraint gadget would falsify the equivalence. The paper must verify that the chosen hole placements and vertex placements eliminate such artifacts for every variable and equation gadget.

    Authors: The construction deliberately positions holes in convex position relative to each gadget so that any line of sight attempting to circumvent a constraint must intersect either the exterior of P or a vertex. We will expand §3.2 in the revision with a short geometric verification for every variable and equation gadget, showing that the chosen vertex coordinates and hole boundaries block all such artifacts. This verification uses only elementary convex geometry and does not lengthen the overall proof substantially. revision: yes

Circularity Check

0 steps flagged

No circularity: standard many-one reduction from known ER-complete problems

full rationale

The paper establishes ER-completeness of the Nesting Bird Box problem via an explicit polynomial-time reduction that constructs polygonal domains with holes whose visibility relations encode an arbitrary polynomial system p(x)=0. The derivation chain relies on geometric gadgets and visibility constraints that are defined independently of the target result; the proof cites prior ER-completeness results for Art Gallery (with holes) and uses recently developed tools, but does not reduce any equation, parameter, or central claim back to a fit or self-citation that is itself defined by the present result. The argument is self-contained against external benchmarks and contains no self-definitional, fitted-prediction, or load-bearing self-citation steps.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The proof rests on standard Euclidean geometry for visibility (open segments avoiding boundaries and vertices) and on the existence of polynomial-time reductions that preserve ER-completeness. No free parameters are fitted and no new entities are postulated.

axioms (2)
  • standard math Visibility is defined by open line segments that intersect neither the exterior of the polygon nor any vertex.
    This is the standard definition used throughout computational geometry for point visibility inside polygonal domains.
  • domain assumption Polynomial-time reductions from known ER-complete problems can be realized by constructing polygonal gadgets with holes that enforce exact visibility constraints.
    The proof technique assumes that the geometric gadgets correctly simulate the algebraic constraints without side effects.

pith-pipeline@v0.9.0 · 5523 in / 1229 out tokens · 36080 ms · 2026-05-14T21:24:23.206635+00:00 · methodology

Review history (2 revisions) →

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

20 extracted references · 20 canonical work pages · 2 internal anchors

  1. [1]

    The art gallery problem is ∃R-complete

    [AAM18] Mikkel Abrahamsen, Anna Adamaszek, and Tillmann Miltzow. The art gallery problem is ∃R-complete. InSTOC’18—Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, pages 65–73. ACM, New York, 2018.doi:10.1145/3188745.3188868. [AAM22] Mikkel Abrahamsen, Anna Adamaszek, and Tillmann Miltzow. The art gallery problem is ∃R-complete....

    work page doi:10.1145/3188745.3188868 2018

  2. [2]

    Covering polygons is even harder

    [Abr22] Mikkel Abrahamsen. Covering polygons is even harder. In2021 IEEE 62nd Annual Symposium on Foundations of Computer Science—FOCS 2021, pages 375–386. IEEE Computer Soc., Los Alamitos, CA, 2022.doi:10.1109/FOCS52979.2021.00045. [AKM21] Mikkel Abrahamsen, Linda Kleist, and Tillmann Miltzow. Training neural networks is er- complete. InAdvances in Neura...

    work page doi:10.1109/focs52979.2021.00045 2021

  3. [3]

    [AKM23] Mikkel Abrahamsen, Linda Kleist, and Tillmann Miltzow

    URL:https://proceedings.neurips.cc/paper/2021/hash/ 9813b270ed0288e7c0388f0fd4ec68f5-Abstract.html. [AKM23] Mikkel Abrahamsen, Linda Kleist, and Tillmann Miltzow. Geometric embeddability of com- plexes is∃R-complete. In39th International Symposium on Computational Geometry, volume 258 ofLIPIcs. Leibniz Int. Proc. Inform., pages Art. No. 1,

    work page 2021

  4. [4]

    Leibniz-Zent

    Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2023.doi:10.4230/lipics.socg.2023.1. [BCHM07] Antonio L Bajuelos, Santiago Canales, Gregorio Hern´ andez, and Ana Mafalda Martins. Solving some combinatorial problems in grid n-ogons. InProceedings of the 7th International Confer- ence on Applied Computer Science (ACS’07), volume 7, pages 151–156,

    work page doi:10.4230/lipics.socg.2023.1 2023

  5. [5]

    Twin-width viii: delineation and win-wins.arXiv preprint arXiv:2204.00722,

    [BCK+22] ´Edouard Bonnet, Dibyayan Chakraborty, Eun Jung Kim, Noleen K¨ ohler, Raul Lopes, and St´ ephan Thomass´ e. Twin-width viii: delineation and win-wins.arXiv preprint arXiv:2204.00722,

    work page arXiv

  6. [6]

    Karp.doi:10.1007/ 978-1-4612-0701-6

    With a foreword by Richard M. Karp.doi:10.1007/ 978-1-4612-0701-6. [BEMM+22] Daniel Bertschinger, Nicolas El Maalouly, Tillmann Miltzow, Patrick Schnider, and Simon Weber. Topological art in simple galleries. In Karl Bringmann and Timothy M. Chan, editors, 5th Symposium on Simplicity in Algorithms, SOSA@SODA 2022, Virtual Conference, January 10-11, 2022, ...

    work page doi:10.1137/1.9781611977066.8 2022

  7. [7]

    A catalog of∃R-complete decision problems about nash equilibria in multi-player games

    [BM16] Vittorio Bil` o and Marios Mavronicolas. A catalog of∃R-complete decision problems about nash equilibria in multi-player games. In Nicolas Ollinger and Heribert Vollmer, editors,33rd Symposium on Theoretical Aspects of Computer Science, STACS 2016, February 17-20, 2016, Orl´ eans, France, volume 47 ofLIPIcs, pages 17:1–17:13. Schloss Dagstuhl - Lei...

    work page 2016

  8. [8]

    An Overview of Minimum Convex Cover and Maximum Hidden Set

    URL:https://doi.org/10.4230/LIPIcs.STACS.2016.17,doi:10.4230/ LIPICS.STACS.2016.17. 22 [Bro24] Reilly Browne. An overview of minimum convex cover and maximum hidden set.arXiv preprint arXiv:2403.01354,

    work page internal anchor Pith review Pith/arXiv arXiv doi:10.4230/lipics.stacs.2016.17 2016

  9. [9]

    Springer-Verlag, Berlin, 1989.doi:10.1007/BFb0089253

    [BS89] J¨ urgen Bokowski and Bernd Sturmfels.Computational synthetic geometry, volume 1355 of Lecture Notes in Mathematics. Springer-Verlag, Berlin, 1989.doi:10.1007/BFb0089253. [Can88a] John Canny.The complexity of robot motion planning, volume 1987 ofACM Doctoral Disser- tation Awards. MIT Press, Cambridge, MA,

    work page doi:10.1007/bfb0089253 1989

  10. [10]

    [CFM+18] Jean Cardinal, Stefan Felsner, Tillmann Miltzow, Casey Tompkins, and Birgit Vogtenhuber

    ACM.doi:10.1145/62212.62257. [CFM+18] Jean Cardinal, Stefan Felsner, Tillmann Miltzow, Casey Tompkins, and Birgit Vogtenhuber. Intersection graphs of rays and grounded segments.J. Graph Algorithms Appl., 22(2):273–295, 2018.doi:10.7155/jgaa.00470. [CH17] Jean Cardinal and Udo Hoffmann. Recognition and complexity of point visibility graphs. Discrete Comput...

    work page doi:10.1145/62212.62257 2018

  11. [11]

    Holmsen, and Tillmann Miltzow

    [DHM19] Michael Gene Dobbins, Andreas F. Holmsen, and Tillmann Miltzow. A universality theorem for nested polytopes.CoRR, abs/1908.02213, 2019.arXiv:1908.02213. [EHP06] Alon Efrat and Sariel Har-Peled. Guarding galleries and terrains.Information Processing Letters, 100(6):238–245,

    work page arXiv 1908

  12. [12]

    [Eid99] Stephan Eidenbenz

    URL:https://www.sciencedirect.com/science/article/ pii/S0020019006001359,doi:10.1016/j.ipl.2006.05.014. [Eid99] Stephan Eidenbenz. How many people can hide in a terrain?Lecture Notes in Computer Science, pages 184–194,

    work page doi:10.1016/j.ipl.2006.05.014 2006

  13. [13]

    Inapproximability of finding maximum hidden sets on polygons and ter- rains.Comput

    [Eid02] Stephan Eidenbenz. Inapproximability of finding maximum hidden sets on polygons and ter- rains.Comput. Geom., 21(3):139–153, 2002.doi:10.1016/S0925-7721(01)00029-3. [Eid06] Stephan Eidenbenz. Finding minimum hidden guard sets in polygons—tight approximability results.Computational Geometry, 34(2):49–57,

    work page doi:10.1016/s0925-7721(01)00029-3 2002

  14. [14]

    Smoothing the gap between NP and ER

    [EvdHM20] Jeff Erickson, Ivor van der Hoog, and Tillmann Miltzow. Smoothing the gap between NP and ER. In2020 IEEE 61st Annual Symposium on Foundations of Computer Science, pages 1022–1033. IEEE Computer Soc., Los Alamitos, CA, 2020.doi:10.1137/20M1385287. [Fis78] Steve Fisk. A short proof of Chv´ atal’s watchman theorem.J. Comb. Theory, Ser. B, 24(3):374,

    work page doi:10.1137/20m1385287 2020

  15. [15]

    [FKM+23] Henry F¨ orster, Philipp Kindermann, Tillmann Miltzow, Irene Parada, Soeren Terziadis, and Birgit Vogtenhuber

    URL:http://dx.doi.org/10.1016/0095-8956(78)90059-X,doi:10.1016/ 0095-8956(78)90059-X. [FKM+23] Henry F¨ orster, Philipp Kindermann, Tillmann Miltzow, Irene Parada, Soeren Terziadis, and Birgit Vogtenhuber. Geometric thickness of multigraphs is∃R-complete.CoRR, abs/2312.05010, 2023.arXiv:2312.05010,doi:10.48550/arXiv.2312.05010. [HM21] Simon B. Hengeveld a...

    work page doi:10.1016/0095-8956(78)90059-x 2023

  16. [16]

    Intersection graphs of segments.J

    [KM94] Jan Kratochv´ ıl and Jiˇ r´ ı Matouˇ sek. Intersection graphs of segments.J. Combin. Theory Ser. B, 62(2):289–315, 1994.doi:10.1006/jctb.1994.1071. [LMM18] Anna Lubiw, Tillmann Miltzow, and Debajyoti Mondal. The complexity of drawing a graph in a polygonal region. InGraph Drawing and Network Visualization: 26th International Symposium, GD 2018, Bar...

    work page doi:10.1006/jctb.1994.1071 1994

  17. [17]

    Intersection graphs of segments and $\exists\mathbb{R}$

    [LMM22] Anna Lubiw, Tillmann Miltzow, and Debajyoti Mondal. The complexity of drawing a graph in a polygonal region.J. Graph Algorithms Appl., 26(4):421–446, 2022.doi:10.7155/jgaa.00602. [Mat14] Jiˇ r´ ı Matouˇ sek. Intersection graphs of segments and∃R.CoRR, abs/1406.2636, 2014.arXiv: 1406.2636. [Mil26] Tillmann Miltzow. Beyond bits: An introduction to c...

    work page internal anchor Pith review Pith/arXiv arXiv doi:10.7155/jgaa.00602 2022

  18. [18]

    [Mn¨ e88] N

    URL: https://arxiv.org/abs/2603.29427,arXiv:2603.29427. [Mn¨ e88] N. E. Mn¨ ev. The universality theorems on the classification problem of configuration varieties and convex polytopes varieties. InTopology and geometry—Rohlin Seminar, volume 1346 of Lecture Notes in Math., pages 527–543. Springer, Berlin, 1988.doi:10.1007/BFb0082792. [MS24] Tillmann Miltz...

    work page doi:10.1007/bfb0082792 1988

  19. [19]

    [Shi17] Yaroslav Shitov

    URL:https: //api.semanticscholar.org/CorpusID:118947850. [Shi17] Yaroslav Shitov. The nonnegative rank of a matrix: hard problems, easy solutions.SIAM Rev., 59(4):794–800, 2017.doi:10.1137/16M1080999. [Sho91] Peter W. Shor. Stretchability of pseudolines is NP-hard. InApplied geometry and discrete mathematics, volume 4 ofDIMACS Ser. Discrete Math. Theoret....

    work page doi:10.1137/16m1080999 2017

  20. [20]

    [vdZBL23] Benito van der Zander, Markus Bl¨ aser, and Maciej Liskiewicz

    doi:10.48550/arXiv.2210.12817. [vdZBL23] Benito van der Zander, Markus Bl¨ aser, and Maciej Liskiewicz. The hardness of reasoning about probabilities and causality.CoRR, abs/2305.09508, 2023.doi:10.48550/arXiv.2305.09508. [Zha92] Xiao-Dong Zhang. Complexity of neural network learning in the real number model. In Workshop on Physics and Computation, pages ...

    work page doi:10.48550/arxiv.2210.12817 2023