{\large

\begin{center}
{\bf ART GALLERY PROBLEMS}
\begin{end}

{\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.

The Minimal Guard Coverage Problem has four input components
\begin{enumarate}
\item [] {\bf Decomposition Type}
\item [] {\bf Shape of Component Pieces }
\item [] {\bf Guard's Place }
\item [] {\bf Polygon Restrictions }
\end{enumarate}


{\bf DECOMPOSING A POLYGON INTO STAR-SHAPED POLYGONS WITHOUT STEINER POINTS}

\medskip

{\bf Problem :} Partition the polygon into star-shaped polygons without
steiner points was studied by the Keil(1984,1985). He proposed a polynomial
time algorithm by using the dynamic programming approach. The complexity of
his algorithm is O(\(n^{7}\log{n}\)). We will try to implement this algorithm
with parallel approach.

{\bf 2. KEIL'S ALGORITHM}

\medskip

The algorithm composed of two parts: preporocessing and Dynamic Programming.

{\bf 2.1 Preprocessing}

\medskip

1. Form the set KER of potential kernel vertices.

2. For each point \(x \in KER\) store a list of the vertices of P that are
visible from x.

3. For each vertex v of P determine the set of vertices of P that are visible
from v and store them in a sorted list.

4. Since each visibility pair \(v_{i}v_{j}\) (\(i<j\)) determined in step 3 is
the base edge of a subpolygon these subpolygons can be sorted by the size
measure \(j-i\) in time O(\(n^{2}\log{n}\)).

5. For each subpolygon \(P_{ij}\) of P form the set of base triangles with
base edge \(v_{i}v_{j}\). ( I think I can directly find this triangles by
grouping the vertices of the subpolygon without applying the algorithm I gave)

\bigskip

{\bf 2.2 Dynamic Programming Part }

\medskip

1. Consider each subpolygon \(P_{ij}\) in the order computed in step 4 of the
preprocessing.

2. Compute the set of a minimum decompositions of \(P_{ij}\) as viewed from
each member of KER.

if j-i = 2, \(P_{ij}\) will consists of a single triangle. Points in KER that
lie in the triangle have real minimum decompositions of \(P_{ij}\). Points
in KER that do not lie in the triangle but are visible from
\(v_{i},v_{i+1}, and v_{j}\) have pseudo minimum decompositions of \(P_{ij}\).

Otherwise for each base triangle \(T_{imj}\) of \(P_{ij}\) for each point
\(x \in KER \):
\begin{itemize}
\item [(a)] If both \(MD_{x}\) of \(P_{im}\) and \(MD_{x}^{\prime}\) of
\(P_{mj}\) exist then they are merged to form a candidate \(M_{x}\) of
\(P_{ij}\).
\item [(b)] If x is visible from \(v_{j}\), then the \(MD_{x}\) of \(P_{im}\)
single merges with \(T_{imj}\). To form the new \(MD_{x}\) of \(P_{ij}\),
the \(MD_{x}\) of \(P_{im}\), \(T_{imj}\) and the smallest MD of \(P_{mj}\)
are combined.
\item [(c)] if x lies in \(T_{imj}\) or x is visible from \(v_{i}\), \(v_{m}\)
and \(v_{j}\) through edge \(v_{i}v_{j}\), then x is the candidate for
\(MD_{x}\) of \(P_{ij}\). This candidate is formed by taking the smallest real
minimum decomposition of \(P_{im}\) together with \(T_{imj}\) and
the smallest real MD of \(P_{im}\).
\end{itemize}

As the various candidates for the \(MD_{x}\) of \(P_{ij}\) are considered
only the smallest is kept. Also the smallest real MD of \(P_{ij}\) will be
needed when no merge past \(v_{i}v_{j}\) is performed.

3. Since the subpolygon \(P_{1n}\)=P, the smallest real minimum decomposion
of \(P_{1n}\) is kept as a minimum star-shaped decomposition of P.

\bigskip

{\bf 2.3 Analysis}

\medskip

Let n denote the number of vertices in the polygon P and N denote the number
of notches in the polygon.

\begin{itemize}
\item Dynamic Programming parts dominates the total complexity of the algorithm.
, its complexity will provide the appropriate upper limit for the complexity
of the algorithm.

\item The test at 2.a, 2.b and 2.c can be done in O(\(\log{n}\)).
\item There are O(\(n^{2}N^{2}\)) points in KER so that O(\(n^{2}N^{2}\log{n}\)) time is spend for each base triangle
\(T_{imj}\).
\item The total complexity of the algorithm is O(\(n^{5}N^{2}\log{n}\))
because there are O(\(n^{3}\)) base triangles.
\end{itemize}

\medskip

{\bf 3. PARALLEL IMPLEMENTATION}

\medskip

\begin{itemize}
\item In step 2 of Dynamic Programming part, minimum decomposition will be
calculated for each element of KER. Also this calculation has to be done
for each base triangle. One possibility to make the parallel the program is
each processor can calculate the minimum decomposition at \(P_{ij}\).
Assume that we have n processors for n element polygon P, then

for(k=1;k<n-2;k++)
  calculate \(P_{(i-k-1)i}\) at processor i.

At step k, each processor examines at most k base triangles for O(\(n^{2}N^{2}\))
points. Then the total complexity of this algorithm will be

\[ O(n^{2}N^{2} \log{n} )+2 \cdot O(n^{2}N^{2} \log{n} ) +3 \cdot O(n^{2}N^{2} \log{n} ) + \vdots
   (n-2) \cdot O(n^{2}N^{2} \log{n} ) \]
\[ = O(n^{2}N^{2} \log{n} ) ( 1+2+3+ \vdots + (n-2))\]
\[ = O(n^{2}N^{2} \log{n} ) \frac{(n-2) \cdot (n-1)}{2} = O(n^{2}N^{2} \log{n} ) \cdot O(n^{2})\]
\[ = O(n^{4}N^{2} \log{n} ) \]

\item The second one is to distribute the total points O(\(n^{2}N^{2}\))
into n processors and let them find the minimum possible decomposition
for the \(P_{ij}\) and apply cube collapse (to find the MD) for the
entry \(P_{ij}\). Since each processor will examine O(\(nN^{2}\)) points, it
will take O(\(nN^{2} \log{n} \cdot n^{3} \)) time to find the minimum decomposition
for each group of points. Then we need to add O(\(\log{n}\)) time to find the
global minimum decomposition of \(P_{ij}\) for each element of DP matrix.
The total coplexity will be O(\( n^{4}N^{2} \log{n} \)).

Let's examine the second step in the algorithm because it helps us to understand
the algorithm so that we can try to figure out other calculations we can do
concurrently. For each entry of matrix P, we need to look at \(O(n^{4})\) points
for the corresponding number of triangles and try to figure out the one who gives
us the minimum value. Let's enumarate the diagonals of the upper matrix (assume
that the main diagonal has 0, the next is 1, and so on) Then the calculations
on each element of the matrix will be like the following

\begin{tabular}{||c|c|c||} \hline
Diagonal Number & Number of Elements & Number of Triangles \\ \hline
2 & (n-2) & 1 \\ \hline
3 & (n-3) & 2 \\ \hline
4 & (n-4) & 3 \\ \hline
\vdots & \vdots & \vdots \\ \hline
(n-1) & 2 & (n-3) \\ \hline
n & 1 & (n-2) \\ \hline
\end{tabular}

We need to this calculations for \(O(N^{4})\) points to find the smallest one
for this entry. Then the total calculation cost can be written as

\[ \sum_{i=2}^{n-1} O(n^{4}) \cdot (n-i) \cdot (i-1)\]

\item Assume that we have \(O(n^{4})\) processors then how we can calculate the
matrix P.
\begin{itemize}
\item [a] Assign each processor a point from KER so that every processor has
either one or no point assign to itself.
\item [b] For each entry of matrix P, we broadcast the appropriate triangle
information to all processors(\(O(\log{n})\)) and each processor do the
necessary calculation for its point.(\(O(\log{n})\)) Then we need to find out
minimum value from these points then we apply the cube collapse algorithm
to figure out the minimum value.(\(O(\log{n})\))
\end{itemize}

The complexity of the algorithm is dominated by the step b. In step b, we
should do this calculation for every entry(\(O(n^{2})\)) and for each
possible triangle(\(O(n)\)) so that the total complexity will be

\[ \underbrace{O(n^{2})}_{number of entries} \cdot
   \underbrace{O(n)}_{number of triangles} \cdot \left(
   \underbrace{O(\log{n})}_{broadcasting triangle info} +
   \underbrace{O(\log{n})}_{calculation} +
   \underbrace{O(\log{n})}_{finding miniumu} \right) \]

\[ O(n^{3}) \cdot (O(\log{n})) = O(n^{3} \cdot \log{n} )\]

\item Assume that we have \(n^{5}\) processor and each \(n^{4}\) processor group calculates
\(o(n^{4})\) points for prespecified triangle then the matrix P can be calculated as
\begin{itemize}
\item [a]  Assign each processor a point from KER and one Triangle so that
every processor has either both or none information.
\item [b] For each entry of matrix P we broadcast the necessary information
to inform which processors will do the calculation and these processors do
their point\-Triangle pair calculation and the minimum result can be obtained
with cube collapse.
\end{itemize}
The complexity of this algorithm will be
\[ \underbrace{O(n^{2})}_{number of entries} \cdot \left(
   \underbrace{O(\log{n})}_{broadcasting info} +
   \underbrace{O(\log{n})}_{calculation} +
   \underbrace{O(\log{n})}_{finding miniumu} \right) \]

\[ O(n^{2}) \cdot (O(\log{n})) = O(n^{2} \cdot \log{n} )\]

\item Can we do this calculation with \(n^{7}\) processors?. Let \(n^{2}\) processors
hold the  matrix P. Assume that we want to calculate the first diagonal,
second diagonal,..etc. To calculate the entry at \(P_{i,j}\) where \(j-i>2\),
we need to calculate values for triangles such as \(P_{i,(i+1)}\) and \(P_{i+1,j}\),
\(P_{i,(i+2)}\) and \(P_{i+2,j}\), etc. The necessary values are not on the same
diagonal then we can not apply pipelining on evaluations of the diagonal values.
\end{itemize}

}