Generalized guarding and partitioning for rectilinear polygons

AbstractA 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)⩽nk+4, with equality for even k. 2.r(n,h,1)=n+4h3+434+43 3.(n,h,2)⩾n6 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