2 papers
cs.CG2026
The Nesting Bird Box Problem is ER-complete: Sharp Hardness Results for the Hidden Set Problem
Lucas Meijer, Till Miltzow, Johanna Ockenfels +1
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…
cs.CG2025
Chasing puppies on orthogonal straight-line plane graphs
Johanna Ockenfels, Yoshio Okamoto, Patrick Schnider
Assume that you have lost your puppy on an embedded graph. You can walk around on the graph and the puppy will run towards you at infinite speed, always locally minimizing the dist…