%% This LaTeX-file was created by <jl> Mon Jan 19 22:58:53 1998
%% LyX 0.11 (C) 1995-1997 by Matthias Ettrich and the LyX Team

%% Do not edit this file unless you know what you are doing.
\documentclass{article}
\usepackage[T1]{fontenc}

\makeatletter


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% LyX specific LaTeX commands.
\newcommand{\LyX}{L\kern-.1667em\lower.25em\hbox{Y}\kern-.125emX\spacefactor1000}

\makeatother

\begin{document}

1/19/98 - day 3


\section{Merge Convex hull }

\begin{enumerate}
\item Sort \( P_{1},...,P_{n} \) by the X value

\end{enumerate}

\paragraph{MCH(\protect\( P_{1},...,P_{n}\protect \))}

\begin{enumerate}
\item \( H_{1} \)= MCE(\( P_{1},...,P_{n/2} \)), \( H_{2} \)= MCE(\( P_{n/2+1},...,P_{n} \))

\item Merge Hull(\( H_{1},H_{2} \))

\end{enumerate}

\subsection{Upper Hull and Lower Hull}

The convex hull algorithm can be built to find the upper hull and the lower
hull then the upper and lower hulls can be easily integrated. 


\paragraph{upper hull: The portion of the points defining the convex hull which spans
from the point with the smallest x value to the point with the largest x value
containing the point with the largest y value.}


\subsection{Upper Merge Hull}

Merge upper hull(\( H_{1},H_{2} \)) = start with the inner (x value near the median point) points,
throwing out those with a y value lower than the maximum.


\subsection{Timing analysis}

\( T(n)=2T(n/2)+c(h_{1}+h_{2}) \) which implies \( T(n)=O(nlg(n)) \)


\section{Quick Hull}

QUH(\( l,P=\{P_{1},...,P_{n}\},r \)) =

\begin{enumerate}
\item find highest point (large y value) m from line \( (l,r) \)

\item remove all points below line \( (l,r) \)

\item QUH(\( l,P,m \)),QUH(\( m,P,r \))

\end{enumerate}

\subsection{Worst case}

The worse case is when every point is on an upper semicircle, causing the time
equation

\( T(n)=T(n-1)+cn \) which means \( T(n)=\Omega (cn^{2}) \)


\subsection{average case}

The average case is points distributed uniformly throughout a semicircle. It
will have time complexity of about: \( T(n)=T(n_{1})+T(n_{2})+cn \) for \( n_{1}+n_{2}\leq \alpha n \) with \( \alpha <1 \).


\section{The ultimate 2d convex hull}

Assume we have a \( O(n) \) time median algorithm.

Upper Hull(\( l,P,r \))

\begin{enumerate}
\item using median partition \( P \) into \( P_{L},P_{R} \) based on the x value

\item Find Bridge b = \( (a,b) \) in upper hull from \( P_{L},P_{R} \)

\item Remove points below the line segments defined by \( (l,a,b,r) \) from \( P_{L},P_{R} \)

\item return Upper Hull(\( l,P_{L},a \)), Upper Hull(\( b,P_{R},r \))

\end{enumerate}

\subsection{Timing}

let \( h= \) \# edges on hull

The time complexity is \( c*n*lg_{2}(h) \).

Check this by plugging it into the time complexity equation.

\( T(n,h)=T(n/2,h_{1})+T(n/2,h_{2})+cn\leq c*n/2*(lg_{2}h_{1}+lg_{2}h_{2})+c*n \)

\( \leq c*n/2*lg_{2}(h^{2}/4)+cn=c*n*lg_{2}(n) \)


\subsection{finding the bridge}


\paragraph{Input: points P partitioned into \protect\( P_{L},P_{R}\protect \)}


\paragraph{Output: Bridge from \protect\( P_{L}\protect \) to \protect\( P_{R}\protect \)}


\paragraph{Support line: line brought in from infinity which just touches the outermost
point of a set of points.}

\begin{enumerate}
\item form \( n/2 \) pars of points from \( P \) and compute their slopes.

\item Find median slope, S.

\item Find support line, SL, with slope S.

\item If SL too steep, throw out left point from each pair s.t. the slope greater
than S, recurse.

\item Else, if SL too shallow, throw out right point from each pair s.t. the slope
< S, recurse.

\item Else if SL has the ``right'' slope you are done

\end{enumerate}

\subsubsection{Timing analysis}

\( n/4 \) points will be thrown out in each recursion.

\( T(n)=T(3/4*n)+cn \) which has solution: \( T(n)=4cn \)

\end{document}