{\bf ART GALLERY PROBLEMS}

{\bf INTRODUCTION }

{\bf Problem(Klee) }

Imagine an art gallery room whose floor plan van be modelled by a polygon
of n vertices.

{\bf Question }: How many stationary guards are needed to guard the room?

Note that, each guard is constrained a fixed point that can see in every
direction, that is, has a 2$\pi$ range of visibility. A guard can not see
through a wall of the room.

{\bf What is visibility ( or visible)?}

A point x can see point y (or y is visible from x) iff the closed segment
$\overline{xy}$ is nowhere exterior to the polygon $P: \overline{xy} \subseteq P$
This definition permits the line-of-sight to have grazing contact with
a vertex.

x has clear visibility to y if $\overline{xy} \subseteq P$ and
$\overline{xy} \cap \partial P \subseteq {x,y}$

A set of guards is said to cover a polygon if every point in the polygon is
visible to some guard. Guards themselves do not block each others visibility.

The guards can see only points of $\partial P$.(Optional)

Klee's question seeks

Express as a function of n, the smallest number of guards that suffice to cover
any polygon of n vertices.

\begin{enumarate}
\item [] necessary - at least that many are needed for some polygon.
\item [] sufficent - that many always suffice for any polygon.
\end{enumarate}

Sufficiency Measures
\begin{enumarate}
\item [] one guard is always necessary
\item [] n guard is the upper limit ( place one guard for each vertex)
\end{enumarate}

Necessary Measures
\begin{enumarate}
\item [] one guard(convex n-gons)
\item [] $\leftfloor \frac{n}{3} \rightfloor$ guard
		 \begin{enumarate}
		 \item [] Fisk's Proof :
				  \begin{enumarate}
				  \item [] Triangulate with diagonals
				  \item [] Apply 3 Coloring
				  \item [] Put guards one specific color
				  \item [] According to pigeon hole principle we need
						   $\leftfloor \frac{n}{3} \rightfloor$ guards.
				  \end{enumarate}
		 \end{enumarate}
\end{enumarate}

Is a guard on every third vertex is sufficient?

If we put guards all the vertices i with $i\equiv m (\mod 3)$ obviously we
can not cover one of $x_{0},x_{1}$ or $x_{2}$.

The Visibility of Interior is different from the Visibility of the boundary.

Guards are placed such that they can see all the paintings on the walls
$\neq >$ guards see the interior.

Guard Types
\begin{enumarate}
\item [] {\bf Vertex Guards} (without Steiner Points) a guard can be located
only a vertex.
\item [] {\bf Point Guards} (with Steiner Points) no restriction on their
location as long as they are inside of the polygon or on the polygon boundary.
\end{enumarate}

Points guards are more powerful then vertex guards.

\begin{enurate}
\item [] {\bf Partition } pieces are not allowed to overlap.
\item [] {\bf Cover }  overlapping is permitted.
\end{enumarate}

The Minimal Guard Coverage Problem has four input components
\begin{enumarate}
\item [] {\bf Decomposition Type} Partition/Cover

		 Covers can be significantly more efficient then partitions.
\item [] {\bf Shape of Component Pieces } Convex, Star, Spinal, Monotone, Trapezoidal,..
\item [] {\bf Guard's Place } (Steiner or not)

		 Steiner points are more efficient and harder to find.

		 A minimum convex partition without Steiner points has no more than
		 four times the number of pieces in a minimal partition with steiner
		 points.

		 We don not have the above result for Star pieces.
\item [] {\bf Polygon Restrictions } (with or without Holes)

		 Convex partitions with Steiner points no hole (polynomial time)

		 Convex partitions with Steiner points with hole(s) (NP-hard)

		 Star cover with holes without Steiner points is NP-hard.

		 Finding a minimal star cover with Steiner points without holes
		 is NP-hard, also.
\end{enumarate}


{\bf Which type of applications do we have for Polygon Decomposition?}

An arbitrary polygonal shape can be recognized more easily once its component
parts have been identified.(Pattern Recognition)

We can solve the problems from bottom-up fashion by solving the components and
get the global solution. Since the components will be uniform, we can apply
special algorithms for these components.

Database systems and graphics are the other application areas.

