The Nesting Bird Box Problem is ER-complete: Sharp Hardness Results for the Hidden Set Problem
This provides a complexity classification for a geometric visibility problem, showing it is as hard as solving polynomial equations over the reals, which is relevant for computational geometry and real algebraic geometry.
The paper proves that the Nesting Bird Box problem, which asks whether a set of k points in a polygonal domain can be placed such that no two see each other, is ER-complete, establishing sharp hardness results for the hidden set problem.
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.