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.