%\documentstyle[fancyheadings,psfig,12pt]{article}
%\pagestyle{fancy}
\documentstyle[psfig,11pt]{article}
\pagestyle{plain}

%\documentstyle[psfig,11pt]{article}
%\documentstyle[twocolumn,psfig]{article}
%\columnsep .2in
\oddsidemargin -.15in
\topmargin -0.55in
\textwidth 6.75in
\textheight 9.2in
\baselineskip = 12 pt
\parindent=2.5em
\parskip=1.5ex
%%%\pagestyle{plain}
%\lhead{Hasan Timucin OZDEMIR }
%\rhead{\today}
\input{psfig}
\title{\vspace{2.0in} 3 DIMENSIONAL DYNAMICAL SURFACE CONSTRUCTION WITH
BEZIER PATCHES \vspace{1.3in} }
\author{ Hasan Timucin OZDEMIR }
\date{\vspace{2.0in} \today}

\begin{document}

{\Large


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

{\bf Problem(Klee) }

Imagine an art gallery room whose floor plan can 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.

\begin{itemize}
\item Points(Steiner) guards are more powerful then vertex guards and harder to find.
\item {\bf Partition } pieces are not allowed to overlap.
\item {\bf Cover }  overlapping is permitted.
\end{itemize}

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

{\bf Applications }

\begin{itemize}
\item 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.

\item Database systems 
\item Computer Graphics 
\end{itemize}

\pagebreak

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

\smallskip

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

\begin{center}
{\bf KEIL'S ALGORITHM}
\end{center}

\smallskip

%\begin{center}
%\fbox{ {\bf Preprocessing} }
%\end{center}

\smallskip

\begin{tabular}{|rp{6in}r|} \hline 
 & \begin{center} {\bf Preprocessing} \end{center} & \\
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}\). & \\  \hline
\end{tabular}

\bigskip

\begin{center}
{\bf Dynamic Programming Part }
\end{center}

\smallskip

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

\begin{center}
{\bf Analysis}
\end{center}

\smallskip

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.

\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}

\pagebreak

\begin{center}
{\bf PARALLEL IMPLEMENTATION}
\end{center}

\smallskip

\begin{itemize}
\item 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^{4}N^{2} \log{n} ) \)

\item 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} \)).

\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
\( O(n^{3} \cdot \log{n} )\)

\pagebreak

\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 \( 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}

}
\end{document}
