Keywords (1)

The Forest Hiding Problem

The Forest Hiding Problem,10.1007/s00454-010-9261-4,Discrete & Computational Geometry,Adrian Dumitrescu,Minghui Jiang

The Forest Hiding Problem   (Citations: 1)
BibTex | RIS | RefWorks Download
Let Ω be a disk of radius R in the plane. A set F of unit disks contained in Ω forms a maximal packing if the unit disks are pairwise interior-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/2log n)-time algorithm that, given a forest with n (not necessarily congruent) disks, computes the boundary illumination map of all disks in the forest.
Journal: Discrete & Computational Geometry - DCG , vol. 44, no. 3, pp. 1566-1579, 2010
Cumulative Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
Sort by: