The forest hiding problem (Q633206)

The authors solve a visibility problem for maximal packings of disks in a large disk \(\Omega\) in the plane. Let \(F\) be a collection of unit disks that form a maximal packing of \(\Omega\), that is, the disks in \(F\) are contained in \(\Omega\), have pairwise disjoint interiors, and it is not possible to add another disk to \(F\) without violating these properties. A point \(p\in \Omega\) is called 'hidden', if any ray emanating from \(p\) hits some disk of \(F\) in a point other than \(p\). Intuitively, the members of \(F\) correspond to trees and the hidden points are the positions in the forest that cannot be seen from outside the forest. The main result is a confirmation of a conjecture due to Joseph Mitchell, stating that there always exist hidden points in the forest, when the radius \(R\) of \(\Omega\) is large enough. It is even shown that there are actually hidden points on the boundaries of at least \(R^2/14\) disks whenever \(R\) is sufficiently large. An example is given illustrating that the use of Euclidean balls is essential for the results to hold. Finally, an \(O(n^{5/2}\log n)\)-time algorithm is presented that allows to compute the boundary illumination map of a given forest \(F\) of \(n\) disks. The boundary illumination map determines for each boundary point of each disk in \(F\) whether it is hidden or not. The algorithm can also be applied in situations where \(F\) is not maximal, and the disks are not congruent.