Generalized Guarding and Partitioning for Rectilinear Polygons


Frank Hoffmann, Klaus Kriegel (joint work with Ervin Györi, Tom Shermer)
Institut für Informatik
Freie Universität Berlin
email: hoffmann@inf.fu-berlin.de
Report B 93-17
December 93

Get the report here or by anonymous ftp:
Server: fubinf.inf.fu-berlin.de
File:   pub/reports/tr-b-93-17.ps.gz

A \tkg\ $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 (or rectangularly visible) from some point contained in $G$. We investigate the function $r(n,h,k)$, which is the largest number of \tkgs\ 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 bounds: \begin{enumerate} \item $r(n,0,k) \leq \fl{n}{k+4}$, with equality for even $k$ \item $r(n,h,1) = \fl{3n+4h+4}{16}$ \item $r(n,h,2) \leq \fl{n}{6}$. \end{enumerate} 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.