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

%\documentstyle[psfig,11pt]{article}
%\documentstyle[twocolumn,psfig]{article}
%\columnsep .2in
\oddsidemargin -.05in
\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}

\begin{center}
{\bf \large CIS600 HOMEWORK \#3 }
\end{center}
\begin{center}
{\bf Prepared by Hasan Timucin OZDEMIR }
\end{center}
\begin{center} \today \end{center}


{\bf 2.} Calculate the delaunay diagram by using both of two sets. The edges of
delaunay diagram is the nearest neighbor of the point. Then we search the
edges whose endpoints are came from the different sets and the length is
minimum. Since we can find the delaunay diagram in \(O(n\log{n})\) and we
can find the minimum length edge in \(O(n)\) time.

\medskip

{\bf 3.} Let \(P_{i} : (x_{i},y_{i})\), \(P_{j} : (x_{j}, y_{j}) \),
\( P_{k} : (x_{k}, y_{k}) \) then
\[ L(i,j) : \frac{x-x_{i}}{y-y_{i}} = \frac{x_{i}-x_{j}}{y_{i}-y_{j}} \]
The vertical distance will be the distance between two points \(P_{k}\) and
\(P_{k}^{\prime}\) such that \(P_{k}^{\prime}\) has the same \(x_{k}\) coordinate
value but \(P_{k}^{\prime}\) is on the L(i,j). Thus,
\[ \frac{x-x_{i}}{y-y_{i}} = \frac{x_{i}-x_{j}}{y_{i}-y_{j}} \]
\[ \frac{y_{i}-y_{j}}{x_{i}-x_{j}} \cdot (x_{k}-x_{i}) = y-y_{i} \]
\[ \frac{y_{i}-y_{j}}{x_{i}-x_{j}} \cdot (x_{k}-x_{i}) + y_{i} = y\]
So the vertical distance \(d_{v}\)
\[ d_{v} = \mid y-y_{k} \mid = \mid \frac{y_{i}-y_{j}}{x_{i}-x_{j}}
 \cdot (x_{k}-x_{i}) + y_{i} - y_{k} \mid \]
Let's look at the distance value in dual plane.
We need to figure out L(i,j,k) on the primal plane,
\[ L(i,j) : \frac{y_{i}-y_{j}}{x_{i}-x_{j}} \cdot x -
\frac{y_{i}-y_{j}}{x_{i}-x_{j}} \cdot x_{i}) + y_{i} = y\]
Since L(i,j,k) is parallel to L(i,j)
\[ L(i,j,k) : y = \frac{y_{i}-y_{j}}{x_{i}-x_{j}} \cdot x + b\]
Let's find the value of b. Since \(P_{k}\) is on L(i,j,k), \(P_{k}\) should
satisfy the line equation
\[ y_{k} = \frac{y_{i}-y_{j}}{x_{i}-x_{j}} \cdot x_{k} + b
\Rightarrow b = y_{k} - \frac{y_{i}-y_{j}}{x_{i}-x_{j}} \cdot x_{k}\]
Then
\[ D_{L(i,j)} : \left( \frac{y_{i}-y_{j}}{x_{i}-x_{j}} ,
y_{i}-\frac{y_{i}-y_{j}}{x_{i}-x_{j}} \cdot x_{k} \right) \]
\[ D_{L(i,j,k)} : \left( \frac{y_{i}-y_{j}}{x_{i}-x_{j}} ,
y_{k}-\frac{y_{i}-y_{j}}{x_{i}-x_{j}} \cdot x_{k} \right) \]
Since these two points are on the same x-coordinate value then the
vertical distance \(d_{v}^{\prime}\)
\[ d_{v}^{\prime} = \mid y_{i}-\frac{y_{i}-y_{j}}{x_{i}-x_{j}} \cdot x_{i} -
y_{k} + \frac{y_{i}-y_{j}}{x_{i}-x_{j}} \cdot x_{k} \mid \]
\[ d_{v}^{\prime} = \mid y_{i} + \frac{y_{i}-y_{j}}{x_{i}-x_{j}} \cdot ( x_{k}-x_{i} ) - y_{k} \mid \]
Since \(d_{v}\) and \(d_{v}^{\prime}\) are equal, the claim is correct.

\medskip

{\bf 4.} We know that if L intersects a polygon P, some of the points on the polygon
is one side of line L and some of the points on the polygon is another side of
the line L. If we map point (a,b) to line y=ax+b and line y=ax+b to point
(-a,b). Then this mapping provides the following

\medskip

{\bf Property : } A point is to the left of a line if and only if the dual line
is to the left of the dual point.

\medskip

n-vertex of convex polygon P in the primal plane defines a convex polygon
in the dual plane. Since the point-line relationship in the primal plane
still holds in the dual plane as a line-point relationship. Thus, the problem
turns out to be a point location in the dual plane. We can do this test in
in \(O(\log{n})\) time, then the algorithm looks like the following

{\bf Preprocessing}
\begin{itemize}
\item [a.] convert each vertex of the polygon in the primal plane to lines in the dual
plane and build the convex polygon in the dual plane. (\(O(n)\))
\item [b.] build the DAG representation of the Kirkpatrick's method in
dual plane. (\( O(n)\))
\end{itemize}

{\bf Query of given line L}
\begin{itemize}
\item [a.] calculate the corresponding point of line L in the dual plane.
\item [b.] find out whether this point is in the convex polygon or not in the
dual plane by using DAG representation. (\(O(\log{n})\))
\end{itemize}


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