Generalized guarding and partitioning for rectilinear polygons
Ervin Győri, Hoffmann, F., Klaus Kriegel, Thomas Caton Shermer · Refubium (Universitätsbibliothek der Freien Universität Berlin) · 1993
Abstract A Tk-guard G in a rectilinear polygon P is a tree of diameter k completely contained in P. The guard G is said to cover a point x if x is visible from some point contained in G. We investigate the function r(n,h,k), which is the largest number of Tk-guards necessary to cover any rectilinear polygon with h holes and n vertices. The aim of this paper is to prove new lower and upper bounds on parts of this function. In particular, we show the following upper bounds: 1. r(n,0,k)⩽ n k+4 , with equality for even k. 2. r(n,h,1)= n+ 4h 3 + 4 3 4+ 4 3 3. (n,h,2)⩾ n 6 These bounds, along with other lower bounds that we establish, suggest that the presence of holes reduces the number of guards required, if k > 1. In the course of proving the upper bounds, new results on partitioning are obtained which also have efficient algorithmic versions.