The Nesting Bird Box Problem is ∃ ℝ \exists\mathbb{R} -complete: Sharp Hardness Results for the Hidden Set Problem
Lucas Meijer, Tillmann Miltzow, Johanna Ockenfels, Miloš Stojaković · 2026
Read The Nesting Bird Box Problem is ∃ ℝ \exists\mathbb{R} -complete: Sharp Hardness Results for the Hidden Set Problem by Lucas Meijer, Tillmann Miltzow, Johanna Ockenfels, Miloš Stojaković (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2604-26749.txt.
Description
Meijer, Miltzow, Ockenfels, and Stojaković show the Nesting Bird Box Problem ER-complete, sharpening hardness results for the Hidden Set Problem. Given a polygonal domain and a number k, the question is whether k points can sit inside it so no two see each other. Each point stands for a birdhouse that birds use only when no occupied neighbor lies nearby. The proof builds on the Art Gallery problem's ER-completeness techniques but runs shorter, using newer tools and hole-punched polygonal domains instead of simple polygons.
Catalog record
| CREATOR | Lucas Meijer, Tillmann Miltzow, Johanna Ockenfels, Miloš Stojaković |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 67298 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2604.26749