The forest hiding problem: an illumination problem for maximal disk packings
Adrian Dumitrescu, Minghui Jiang · 2010
Let Ω be a disk of radius R in the plane. A set F of closed unit disks contained in Ω forms a maximal packing if the unit disks are pairwise disjoint and the set is maximal: i.e., it is not possible to add another disk to F while maintaining the packing property. A point p is hidden within the “forest ” defined by F if any ray with apex p intersects some disk of F: that is, a person standing at p can hide without being seen from outside the forest. We show that if the radius R of Ω is large enough, one can find a hidden point for any maximal packing of unit disks in Ω. This proves a conjecture of Joseph Mitchell. We also present an O(n 5/2 log n)-time algorithm that, given a forest with n (not necessarily congruent) disks, computes the boundary illumination map of all disks in the forest. 1