% Template article for preprint document class `elsart'
% SP 2001/01/05

% Modified 2007/01/09 for CTW 2010
% Please find the original file at http://www.elsevier.com/

\documentclass{ctwart}

% Use the option doublespacing or reviewcopy to obtain double line spacing
% \documentclass[doublespacing]{elsart}

% if you use PostScript figures in your article
% use the graphics package for simple commands
% \usepackage{graphics}
% or use the graphicx package for more complicated commands
% \usepackage{graphicx}
% or use the epsfig package if you prefer to use the old commands
% \usepackage{epsfig}

% The amssymb package provides various useful mathematical symbols
\usepackage{graphicx,amssymb}
% defining environment
\newtheorem{theorem}{Theorem}
\newtheorem{invar}{Invariant}
\newtheorem{lemma}[theorem]{Lemma}
%\newtheorem{cor}[theorem]{Corollary}
\newtheorem{obs}{Observation}
%\newtheorem{conj}{Conjecture}
%\newtheorem{prop}[theorem]{Proposition}

\def\QED{\ensuremath{{\square}}}
\def\markatright#1{\leavevmode\unskip\nobreak\quad\hspace*{\fill}{#1}}
\newenvironment{proof}
  {\begin{trivlist}\item[\hskip\labelsep{\bf Proof.}]}
  {\markatright{\QED}\end{trivlist}}


\begin{document}
\setcounter{page}{137}
\begin{frontmatter}

% Title, authors and addresses

% use the thanksref command within \title, \author or \address for footnotes;
% use the corauthref command within \author for corresponding author footnotes;
% use the ead command for the email address,
% and the form \ead[url] for the home page:
% \title{Title\thanksref{label1}}
% \thanks[label1]{}
% \author{Name\corauthref{cor1}\thanksref{label2}}
% \ead{email address}
% \ead{pinciuv1@southernct.edu}
% \ead[url]{home page}
% \thanks[label2]{}
% \corauth[cor1]{}
% \address{Address\thanksref{label3}}
% \thanks[label3]{}

\title{Pixel Guards in Polyominoes}

% use optional labels to link authors explicitly to addresses:
% \author[label1,label2]{}
% \address[label1]{}
% \address[label2]{}

\author{Val Pinciu}

\address{Department of Mathematics, Southern Connecticut State University, New Haven, CT 06515}

\begin{keyword}
% keywords here, in the form: keyword \sep keyword
art gallery problem \sep pixel \sep polyomino
\end{keyword}

\end{frontmatter}

% main text
\section{Introduction}
\label{}
%\linebreak 
The original art gallery problem, posed by Klee in 1973, asks to find the minimum number of guards
sufficient to cover any polygon with $n$ vertices. The first solution to this problem was given by Chv\'atal ~\cite{Chvatal}, who proved that  $\lfloor n/3\rfloor$ guards are sometimes necessary, and always sufficient to cover a polygon with $n$ vertices. Later Fisk \cite{Fisk} provided a shorter proof of Chv\'atal's theorem using an elegant graph coloring argument. Klee's art gallery problem has since grown into a significant area of study.
Numerous {\em art gallery problems} have been proposed and studied with different restrictions 
placed on the shape of the galleries or the powers of the guards. (See the monograph by O'Rourke
~\cite{ORourke87}, and the surveys by Shermer~\cite {Shermer} and Urrutia~\cite{Urrutia}.) 
%Art gallery problems are studied by mathematicians and computer scientists because 
%they are fundamental visibility problems, and visibility is a central issue in many
%computing applications. Application areas for visibility include robotics, 
%motion planning, vision, graphics, computer--aided architecture, and pattern recognition.
%Other reasons that art gallery problems are studied are that
%they are a continuous form of classical facility--location problems, have simple
%formulation, and require an interesting interplay of graph theory, geometry, and computer
%science in their solution.
\\
\linebreak 
In this paper we consider a variation of the art gallery problem where the gallery is an {\em $m$-polyomino}, consisting of a connected union of $m$ $1\times 1$ unit squares called {\em pixels}.
Throughout this paper $P_m$ denotes an $m$-polyomino.
We say that a point $a \in P_m$ {\em covers\/} a 
point $b \in P_m$ provided $a=b$, or the line segment 
$ab$ does not intersect the exterior of $P_m.$ 
%(Every point in $P_m$ covers itself.)
We say that a pixel $A$ {\em covers} a point $b$, provided some point $a \in A$ covers $b$. 
A set of points $G$ is called a {\em point guard set} for $P_m$ if for every point $b \in P_m$ there is point $a \in G$ such that $a$ covers $b$.
A set of pixels ${\mathcal G}$ is called a {\em pixel guard set} for $P_m$ if for every point $b \in P_m$ there is a pixel $A \in {\mathcal G}$ such that $A$ covers $b$.
\\
\linebreak
In \cite{Irfan}, Irfan et al. show that $\lceil \frac{m-1}{3} \rceil$ point guards are sufficient and sometimes necessary to cover any $m$-polyomino $P_m$, with $m \ge 2$. They also note that $\lceil \frac{m-1}{3} \rceil$ is an upper bound for the minimum number of pixel guards sufficient to cover any $m$-polyomino. In this paper we improve this bound, showing that an $m$-polyomino always has a pixel guard set of cardinality $\lfloor \frac{m+1}{11}\rfloor + \lfloor\frac{m+5}{11}\rfloor + \lfloor \frac{m+9}{11}\rfloor$. We also show that this bound is sharp, by constructing $m$-polyominoes that require exactly $\lfloor \frac{m+1}{11}\rfloor + \lfloor\frac{m+5}{11}\rfloor + \lfloor \frac{m+9}{11}\rfloor$ pixel guards.
%\section{Necessity of $\lfloor \frac{m+1}{11}\rfloor + \lfloor\frac{m+5}{11}\rfloor + \lfloor \frac{m+9}{11}\rfloor$ pixel guards}
\section{Main Results}
Here is our main result:
\begin{thm}
For any $m$-polyomino $P_m$ with $m \ge 2$, 
$\lfloor \frac{m+1}{11}\rfloor + \lfloor\frac{m+5}{11}\rfloor + \lfloor \frac{m+9}{11}\rfloor$
pixel guards are always sufficient, and sometimes necessary to cover $P_m$.
\end{thm}
\begin{proof}
We will use a construction to prove the necessity part of our result. The polyomino $P_{11k+2}$ from Figure \ref{lowerbound} has $3+7k+4(k-1)+3=11k+2$ pixels. The dual graph of this polyomino is a tree with $1+2k+(k-1)+1=3k+1$ leaves. Since two pixels that correspond to a leaf cannot be guarded by the same pixel guard, then the number of pixels required to guard $P_{11k+2}$ is at least $3k+1$. Simple alterations of this construction can provide examples of $m$-polyominos that require at least $\lfloor \frac{m+1}{11}\rfloor + \lfloor\frac{m+5}{11}\rfloor + \lfloor \frac{m+9}{11}\rfloor$ pixel guards, for any integer $m \ge 2$. Next we will prove several technical lemmas, and the sufficiency will follow from Proposition \ref{upperbound}. 
\end{proof}
\begin{figure}[h]
  \centering
  \includegraphics[width=.8\columnwidth]{pixel.eps}
  \caption{An $(11k+2)$-polyomino that requires $3k+1$ pixel guards.}
  \label{lowerbound}
\end{figure}
%\section{Sufficiency of $\lfloor \frac{m+1}{11}\rfloor + \lfloor\frac{m+5}{11}\rfloor + \lfloor \frac{m+9}{11}\rfloor$ pixel guards}
%Before we prove the sufficiency part of our proof, we need several technical lemmas.
\begin{lemma}
\label{function}
For each positive integer $m$ we define
\[ 
f(m)= \bigg\lfloor {m+1\over 11}\bigg\rfloor + \bigg\lfloor {m+5\over 11}\bigg\rfloor + \bigg\lfloor {m+9\over 11}\bigg\rfloor
\]
Then the following are true:
\begin{enumerate}
\item $f(m+3) \le f(m)+1 \le f(m+4)$ for all positive integers $m$.
\item $f(m+7) \le f(m)+2 \le f(m+8)$ for all positive integers $m$.
\item $f(m+11)=f(m)+3$ for all positive integers $m$.
\item $f(m+n-2) \ge f(m)+f(n)-1$ for all positive integers $m$ and $n$.
\end{enumerate}
\end{lemma}

\begin{lemma}
\label{decomposition}
For any $m$-polyomino $P_{m}$ with $m \ge 13$, there exists a $k$, $4\le k \le 10$ such that $P_m$ is the union of a $k$-polyomino $P_k$ and an $(m-k)$-polyomino $P_{m-k}$. Moreover, if the smallest $k$ that satisfies this property is $k=10$, then we can assume that exactly one pixel of $P_{m-10}$ is adjacent to $P_{10}$. 
\end{lemma}
\begin{proof}
Given an $m$-polyomino $P_m$, let $G_m^*$ be the dual graph of $P_m$, and let $T_m$ be a spanning tree of $G_m^*$. Since every vertex of $G_m^*$ has maximum degree 4, we can look at $T_m$ as a rooted trinary tree. For simplicity, we will label the vertices of the rooted tree as the corresponding pixels in the dual polyomino. We will also transfer the common terminology from rooted trees (child, parent, sibling, etc) to the corresponding pixels. 
For any vertex $A$ of $T_m$ that is not the root, we can obtain a spanning forest of $G_m^*$ with two components, by deleting the edge that connects $A$ with its parent. These two componenets will generate a decomposition of $P_m$ into two polyominoes: a $k$-polyomino $P_k$ that contains $A$, called the {\em polyomino generated by $A$ and $T_m$}, and another polyomino $P_{m-k}$ that does not contain $A$. If $B$ is a pixel of $P_{m-k}$ and $C$ is a pixel of $P_k$ such that $B$ and $C$ are adjacent, we can create another spanning tree $T_m'$ of $G_m^*$ by replacing the edge that connects $C$ with its parent in $T_m$ with the edge $BC$. We will call this an {\em adoption} and say that $B$ adopted $C$. An adoption will transfer a pixel of the polyomino generated by $A$, and all its descendants to the complementary polyomino. 
Now if $h$ is the height of $T_m$, we consider the pixels of level $h-1$, $h-2$, $h-3$, or $h-4$ that have at least three descendants.  Obviously this set is not empty. Let $A$ be such a pixel with a minimum number of descendants. Then one can show that the polyomino generated by $A$ satisfies the conditions of the proposition, or we can do an adoption to decrease the number of descendants of $A$.
\end{proof}
\begin{lemma}
\label{basicstep}
\begin{enumerate}
\item One pixel guard is always sufficient to cover any 5-polyomino.
\item Two pixel guards are always sufficient to cover any 9-polyomino.
\item Three pixel guards are always sufficient to cover any 12-polyomino.
\end{enumerate}
\end{lemma}

\begin{prop}
\label{upperbound}
For any $m$-polyomino $P_m$, if $m\ge 2$, then 
$\lfloor \frac{m+1}{11}\rfloor + \lfloor\frac{m+5}{11}\rfloor + \lfloor \frac{m+9}{11}\rfloor$ pixel guards are sufficient to cover $P_m$.
\end{prop}
\begin{proof}
The proof of this proposition is by induction on $m$.
If $2 \le m \le 12$, the statement follows from Lemma \ref{basicstep}.
If $m \ge 13$, then by Lemma \ref{decomposition}, $P_m$ is the union of a $k$-polyomino $P_k$ and an $(m-k)$-polyomino $P_{m-k}$, where $4\le k \le10$. Assume $k$ is the smallest with this property. Let $f(m)$ be the function from Lemma \ref{function}. Then by induction hypothesis the minimum number of pixel guards required to watch $P_{m-k}$ is $g(P_{m-k}) \le f(m-k)$.
\\
If $k=4$ or $k=5$, we obtain:
\\
$
g(P_m) \le g(P_k) + g(P_{m-k}) \le 1 +g(P_{m-k}) \le 1+ f(m-4) \le f(m).$
\\
If $k=8$ or $k=9$, we obtain:
\\
$g(P_m) \le g(P_k) + g(P_{m-k}) \le 2 +g(P_{m-k}) \le 2+ f(m-8) \le f(m).$
\\
\\
If $k=6$, we should note that 33 out of the 35 possible hexaminoes can be covered by only one pixel guard, and we can use an argument similar with the case $k=4$ or $k=5$. Otherwise, if $P_k$ requires two pixel guards, let $A$ be the pixel that generated $P_k$, and let $B$ be the parent of $A$. If $B$ is the only pixel in $P_{m-k}$ adjacent to $P_k$, then one can show that $P_{m-k}$ has a pixel guard set of cardinality $f(m-4)$ that contains $B$. 
%(induction hypothesis to the polyomino obtained by the union of $P_{m-6}$, $A$, and one of $A$'s children.) 
Then $B$ can also be used to guard part of $P_k$, and we need only one additional guard. Otherwise, let $C$ be a pixel in $P_{m-k}$ adjacent to $P_k$. Then $C$ can adopt a descendant of $A$, reducing the problem to the case $k=4$ or $k=5$, or $C$ is a leaf, in which case we can remove $B$ and $C$ from $P_{m-k}$, add them to $P_k$, and reduce the problem to the case $k=8$. (note that the minimality of $k$ was not used in the case $k=8$.)
\\
If $k=7$,  let $A$ be the pixel that generated $P_k$, and let $B$ be its parent. Then this case can also be reduced to the one of the cases $k=4$, $k=5$, or $k=8$, or we can show that $B$ has exactly two children. In this last case, let $C$ be the other child of $B$, and let $D$ be the parent of $B$. If in $T_m$ we remove the edge $BC$, and the edge that connects $D$ with its parent, we can obtain a decomposition of $P_m$ into three polyominos. One of them is 9-polyomino. Using the induction hypothesis and Lemma \ref{function} we obtain:
\\
$g(P_m) \le g(P_9) + g(P_{l}) +g(P_{m-l-9}) \le 2 +f(l)+f(m-l-9)$
\\
$\le 2+f(l+m-l-9-2)+1 =3+f(m-11)=f(m).$
\\
Finally, if $k=10$, since $k$ is the smallest that satisfies the property from Lemma \ref{decomposition}, we can assume that exactly one pixel of $P_{m-10}$ is adjacent to $P_{10}$. Then by removing this pixel from $P_{m-10}$, and adding it to $P_{10}$, we can assume that $P_m$ is the union of an 11-polyomino $P_{11}$ and an $(m-11)$-polyomino $P_{m-11}$. Then 
$g(P_m) \le g(P_{11}) + g(P_{m-11}) \le 3 +g(P_{m-11}) \le 3+ f(m-11) = f(m).$
\end{proof}
% The Appendices part is started with the command \appendix;
% appendix sections are then done as normal sections
% \appendix

% \section{}
% \label{}

\begin{thebibliography}{00}

% \bibitem{label}
% Text of bibliographic item

% notes:
% \bibitem{label} \note

% subbibitems:
% \begin{subbibitems}{label}
% \bibitem{label1}
% \bibitem{label2}
% If there is a note, it should come last:
% \bibitem{label3} \note
% \end{subbibitems}


\bibitem{Chvatal}
V. Chv\'atal,
A combinatorial theorem in plane geometry:
{\em J. Combin. Theory Ser. B\/} {\bf 18} (1975) 39--41.

\bibitem{Fisk}
S. Fisk,
A short proof of Chv\'atal's watchman theorem:
{\em J. Combin. Theory Ser. B\/} {\bf 24} (1978) 374.

\bibitem{Irfan}
M. Irfan, J. Iwerks, J. Kim, J. Mitchell,
Guarding Polyominoes:
{\em 19th Annual Workshop on Computational Geometry\/} (2009).

\bibitem{ORourke87}
J. O'Rourke:
{\em Art Gallery Theorems.\/} Oxford University Press, 1987.
  
\bibitem{Shermer}
T.C. Shermer:
Recent results in art gallery theorems,
{\em Proc. IEEE\/} {\bf 80} (1992) 1384--1399.

\bibitem{Urrutia}
J. Urrutia:
Art gallery and illumination problems, in:
{\em Handbook of Computational Geometry, } J.-R Sack and J. Urrutia (Eds.), 
Elsevier Science B. V., 1999, 
pp. 973--1027.

\end{thebibliography}

\end{document}

