%\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.95in
\textwidth 6.55in
\textheight 9.5in
\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 ART GALLERY PROBLEMS}
\end{center}

{\bf INTRODUCTION }

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

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

A point x can {\bf see} point y (or y {\bf 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 {\bf clear visibility} to y if $\overline{xy} \subseteq P$ and
$\overline{xy} \cap \partial P \subseteq {x,y}$

\begin{figure}[htbp]
\centerline{\psfig{file=zfig1.ps,height=1.5in,width=3in}}
\caption{Visibility }
\label{fig:layers}
\end{figure} 

A set of guards is said to {\bf 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)

\begin{figure}[htbp]
\centerline{\psfig{file=figart18.ps,height=3in,width=5in}}
\caption{}
\label{fig:layers}
\end{figure}

\begin{figure}[htbp]
\centerline{\psfig{file=figart19.ps,height=2in,width=5in}}
\caption{}
\label{fig:layers}
\end{figure}

\begin{figure}[htbp]
\centerline{\psfig{file=zfig2.ps,height=2.5in,width=5in}}
\caption{}
\label{fig:layers}
\end{figure}

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{itemize}
\item [] {\bf necessary} - at least that many are needed for {\bf some polygon}.
\item [] {\bf sufficent} - that many always suffice for {\bf any polygon}.
\end{itemize}

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

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

{\bf Is a guard on every third vertex is sufficient?}


\begin{figure}[htbp]
\centerline{\psfig{file=figart10.ps,height=2in,width=5in}}
\caption{}
\label{fig:layers}
\end{figure}

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

{\bf The Visibility of Interior is different from the Visibility of the boundary}.

\begin{figure}[htbp]
\centerline{\psfig{file=figart11.ps,height=2in,width=3in}}
\caption{}
\label{fig:layers}
\end{figure}

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

Guard Types
\begin{itemize}
\item [] \hspace{0.5in} {\bf Vertex Guards} (without Steiner Points) a guard can be located
only a vertex.
\item [] \hspace{0.5in} {\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{itemize}

Points guards are more powerful then vertex guards.

\begin{figure}[htbp]
\centerline{\psfig{file=figart12.ps,height=2in,width=3in}}
\caption{}
\label{fig:layers}
\end{figure}

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

The Minimal Guard Coverage Problem has four input components
\begin{itemize}
\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)

\begin{figure}[htbp]
\centerline{\psfig{file=figart13.ps,height=1.6in,width=5in}}
\caption{}
\label{fig:layers}
\end{figure}

		 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{itemize}


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

\medskip

\begin{center}
{\bf \Large DECOMPOSING A POLYGON INTO STAR-SHAPED POLYGONS WITHOUT STEINER POINTS}
\end{center}
%\begin{center}
%{\bf Prepared by Hasan Timucin OZDEMIR }
%\end{center}
%\begin{center} \today \end{center}


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

I summarize the some information from the Keil's paper[1] in the following
part.

\bigskip

{\bf 1. DEFINITIONS}

\medskip

{\bf Definition 1} : If the interior angle at a vertex is greter than
180(reflex) the vertex is called {\bf notch}.

{\bf Definition 2} : Let P be a polygon in the plane having vertices
\(v_{1},v_{2},v_{3},\cdots,v_{n}\) clockwise on its boundary.
If a vertex x is a notch or \(v_{1}\) or \(v_{n}\), then it is
called {\bf reference vertex} of P.
A vertex x is called {\bf convex vertex} if it is not a reference vertex.

{\bf Definition 3} : A {\bf Star-shaped Polygon} is a polygon in which the
entire polygon is visible from at least one fixed(possibly interior) point of
the polygon.

{\bf Definition 4} : A {\bf pseudo star-shaped Polygon} \(PS_{ij}\) of P
based along \(v_{i}v_{j}\) has the property that there exists a point x in P
and not in \(PS_{ij}\) so that every point of \(PS_{ij}\) can be seen from
x through \(v_{i}v_{j}\).

{\bf Definition 5} : Let P be a polygon in the plane having vertices
\(v_{1},v_{2},v_{3},\cdots,v_{n}\) clockwise on its boundary.
A subpolygon is called a {\bf valid subpolygon} when either i=1 or j=n or at
least one of \(v_{i}\) and \(v_{j}\) is a notch.
A valid subpolygon \(P_{ij}\)is divided into three class;
\begin{itemize}
\item [] {\bf type a :} if both \(v_{i}\) and  \(v_{j}\) are reference vertices.
\item [] {\bf type b :} if \(v_{i}\) is a reference vertex and  \(v_{j}\) is
convex vertex.
\item [] {\bf type b :} if \(v_{i}\) is convex vertex and  \(v_{j}\) is a
reference vertex.
\end{itemize}

{\bf Definition 6} : Two points of a polygon P are said to be {\bf visible}
if the line segment joining them lies whooly inside P.

{\bf Definition 7} : Let P be a polygon in the plane having vertices
\(v_{1},v_{2},v_{3},\cdots,v_{n}\) clockwise on its boundary.
A {\bf subpolygon} \(P_{ij}\) of P with vertices
\(v_{i},v_{i+1},\cdots,v_{j}\) exists when \(1 \leq i < j-1 \leq n-1\), and
\(v_{i}v_{j}\) are visible.

{\bf Definition 8} : Let P be a polygon in the plane having vertices
\(v_{1},v_{2},v_{3},\cdots,v_{n}\) clockwise on its boundary.
The {\bf base convex polygon} \(C_{ij}\) of a minimum decomposition (MD) D
of \(P_{ij}\) is that convex polygon of D that contains the edge \(v_{i}v_{j}\)
in its boundary. \(v_{i}v_{j}\) is called {\bf base edge} of \(P_{ij}\).

{\bf Definition 9} : Let P be a polygon in the plane having vertices
\(v_{1},v_{2},v_{3},\cdots,v_{n}\) clockwise on its boundary.
The {\bf base triangle} \(T_{imj}\) of \(P_{ij}\) is a triangle \(v_{i}v_{m}v_{j}\)
\((i<m<j)\) where each of \(v_{i}v_{m}\) and \(v_{m}v_{j}\) is either
a base edge of a valid subpolygon or an original side of P.

{\bf Definition 10} : Let P be a polygon in the plane having vertices
\(v_{1},v_{2},v_{3},\cdots,v_{n}\) clockwise on its boundary.
The set of polygons from which the entire polygon P is visible is called the
{\bf kernel} of P.

{\bf Definition 11} : Let P be a polygon in the plane having vertices
\(v_{1},v_{2},v_{3},\cdots,v_{n}\) clockwise on its boundary.
Let \(S_{im}(A)\) be the base star-shaped polygon of the minimum star-shaped
decomposition A of \(P_{im}\). A triangle \(T_{imj}\) can {\bf single-merge}
with a minimum decomposition A of \(P_{im}\) if \(S_{im}(A) \cup T_{imj}\) is a
star-shaped polygon.

{\bf Definition 12} : Let P be a polygon in the plane having vertices
\(v_{1},v_{2},v_{3},\cdots,v_{n}\) clockwise on its boundary.
Let \(S_{im}(A)\) be th base star-shaped polygon of the minimum star-shaped
decomposition A of \(P_{im}\). A triangle \(T_{imj}\) can {\bf double-merge}
with a minimum decomposition A of \(P_{im}\) and a minumum decomposition B
of \(P_{mj}\) if \(S_{im}(A) \cup T_{imj} \cup S_{mj}(B) \) is a
star-shaped polygon.

{\bf Definition 13} : ({\bf KER- Potential Kernel Points}) If \(v_{a}\) and
\(v_{b}\) are vertices of polygon P then there may exist a segment of the
line through \(v_{a}\) and \(v_{b}\), that lies entirely within P, that
contains \(v_{b}\) and exactly one other boundary point \(v_{c}\) of P so that
\(v_{b}\) lies between \(v_{a}\) and \(v_{c}\). This segment denoted by
\(I_{ab}\) that is a segment drawn inside P beginning at \(v_{b}\), in the
direction away from \(v_{a}\), until the boundary of P is reached. The set of
segments L can be defined as L=\( \{ I_{ab} \mid v_{b}\) is a notch and \(v_{a}\)
is a vertex of P visible from \(v_{b} \} \). The segments in L may intersects
with each other or with sides of P or both. The {\bf KER} denote the set of
all such intersections together with the vertices of P.

\begin{figure}[htbp]
\centerline{\psfig{file=figart14.ps,height=2in,width=5in}}
\caption{ }
\label{fig:layers}
\end{figure}

\bigskip

{\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. Since the Dynamic Programming part dominates the
total complexity of the algorithm, its complexity will provide the
appropriate upper limit for the complexity of the algorithm. The test at 2.a,
2.b and 2.c can be done in O(\(\log{n}\)). 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}\). The total complexity of the algorithm is O(\(n^{5}N^{2}\log{n}\))
because there are O(\(n^{3}\)) base triangles.

\bigskip

\begin{figure}[htbp]
\centerline{\psfig{file=figart15.ps,height=2in,width=5in}}
\caption{ }
\label{fig:layers}
\end{figure}

\begin{figure}[htbp]
\centerline{\psfig{file=figart16.ps,height=2in,width=5in}}
\caption{ }
\label{fig:layers}
\end{figure}

\begin{figure}[htbp]
\centerline{\psfig{file=figart17.ps,height=2in,width=4in}}
\caption{ }
\label{fig:layers}
\end{figure}

{\bf 2.4 How can we find the Base Triangles}

\medskip

1. Determine which vertices are notches in O(n) time.

2. For each reference vertex x of P determine the set of vertices of P visible
from x. For convex vertices store the set of visible reference vertices. Denote
such a visibility list sorted by angle about vertex x as V(x). All of this can be
done in O(nN) time using the visibility polygon algorithm of El-Gindy and Avis.
(A visiblility polygon from a point inside the polygon P can be mode in O(n) time.
Since there are N notches, it takes O(nN) time to get the visibility polygon of
each notch.)

3. Since each visibility pair \(v_{i}v_{j}\) ($i<j$) determined in step 2 is the
base edge of a valid subpolygon these valid subpolygons can be sorted in
ascending order by the size measured \(j-i\)
(This denotes the number of vertices in the subpolygon - 1)
in time O(\(nN\log{nN}\)).

4. For each subpolygon \(P_{ij}\) form the set of base triangles. In the
\(O(N^{2})\) subpolygons of {\bf type a} this can be done in O(n) time by
computing T=\( \{ \left(  V_{i} \cup \{ v_{i+1} \} \right) \cap
\left( V_{j} \cup \{ v_{j-1} \} \right) \} \).
In the O(nN) subpolygons of {\bf type b } or {\bf c} this can be done
in O(\(N\log{n}\)) time by computing T using a binary search.

\pagebreak


{\bf 3. PARALLEL IMPLEMENTATION}

\medskip

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 program parellel is
to let each processor 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} ) + \cdots
   (n-2) \cdot O(n^{2}N^{2} \log{n} ) \]
\[ = O(n^{2}N^{2} \log{n} ) ( 1+2+3+ \cdots + (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} ) \]

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

\bigskip

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)\]

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\hspace{0.1cm} of\hspace{0.1cm} entries} \cdot
   \underbrace{O(n)}_{number\hspace{0.1cm} of\hspace{0.1cm} triangles} \cdot \left(
   \underbrace{O(\log{n})}_{broadcasting\hspace{0.1cm} triangle\hspace{0.1cm} info} +
   \underbrace{O(\log{n})}_{calculation} +
   \underbrace{O(\log{n})}_{finding\hspace{0.1cm} minimum} \right) \]

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

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\hspace{0.1cm} of\hspace{0.1cm} entries} \cdot \left(
   \underbrace{O(\log{n})}_{broadcasting\hspace{0.1cm} info} +
   \underbrace{O(\log{n})}_{calculation} +
   \underbrace{O(\log{n})}_{finding\hspace{0.1cm} minimum} \right) \]

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

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.


{\bf References}

\medskip

[1] Keil, J. Mark, "Decomposing a Polygon into Simpler Components",
	SIAM J. Computing, Vol. 14, No: 4, November 1985, pp 799-817

[2] O'rourke, Joseph, Art Gallery Theorems and Algorithms, Oxford Press,1987

[3] O'rourke, Joseph, Computational Geometry in C, Cambridge University
Press, 1993


%\begin{figure}[htbp]
%\centerline{\psfig{file=CIS710_3f1.ps,height=2in,width=5in}}
%\caption{Odd-Even Sort on Hypercube }
%\label{fig:layers}
%\end{figure}

\end{document}
