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

CREATORLucas Meijer, Tillmann Miltzow, Johanna Ockenfels, Miloš Stojaković
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE67298
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2604.26749

Browse the full library · About the Tower of Babel