%% This LaTeX-file was created by <jl> Sun Jan 18 14:39:17 1998
%% LyX 0.12 (C) 1995-1998 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}

day 2 1/14/98


\section{Sorting vs. Convex hull}


\subsection{sorting algorithms}

A lower bound on the time complexity of sorting algorithms given only the use
of a compare primitive, \emph{compare(a,b)}, which returns (a < b) is \( \Omega (\log _{2}n!)\approx \Omega (n\log _{2}n) \). You
can see this by noting that there are \( n! \) possible outcomes to sorting \( n \) elements
which implies that \( \log _{2}n! \) choices must be made.


\subsubsection{Insertion sort}

Insert each element into a (balanced) binary tree, then traverse the tree in
order to find the sort


\subsubsection{heap sort}

Place all the elements into a heap and pull them out of the heap in order


\subsubsection{merge sort}

Split the elements into 2 equal size subsequences, sort each subsequence, then
merge the two sorted subsequences.


\subsubsection{median sort}


\paragraph{deterministic version}

let Sort(P) =

m = Median(P)

return \( Sort(\{P_{i}:P_{i}<m\}) \):m: \( Sort(\{P_{i}:P_{i}>m\}) \)

This differs from merge sort, becuase the work at a particular level occurs
before recursing so only a concatentation is necessary on return.


\paragraph{randomized version}

Otherwise known as quicksort.

let QSort(P) =

m = Random(P)

return \( Sort(\{P_{i}:P_{i}<m\}) \):m: \( Sort(\{P_{i}:P_{i}>m\}) \)


\subsection{Convex hull algorithms}


\subsubsection{The primitive operations of convex hull algorithms}

\begin{itemize}
\item testing if 2 line segments intersect, \emph{bool Intersect(Line\_segment\_1,Line\_segment\_2)}
\item testing if a point lies to the left or to the right the line derived from a
line segment, \emph{LR\_test(Line\_segment,Point) = \( Sign(Det(\left[ \begin{array}{ccc}
LS_{11} & LS_{12} & 1\\
LS_{21} & LS_{22} & 1\\
P_{31} & P_{32} & 1
\end{array}\right] )) \)} where \( LS_{1j} \) = the components of the starting point of the line segment and \( LS_{2j} \) =
the components of the ending point of the line segment. If the output is positive,
\emph{Point} lies to the left of the line defined by the line segment
\end{itemize}

\subsubsection{definitions}

\begin{itemize}
\item \( A\subseteq R^{2} \) is a set in the plane
\item \( CH(A)= \) simplest convex set conatining A
\item \( A\subseteq R^{2} \) is convex if forall \( \forall p_{1},p_{2}\in A\Rightarrow LineSegment(P_{1},P_{2})\subseteq A \) 
\end{itemize}

\subsubsection{Convex hull heap sort analog = Graham scan}

Graham Scan(\( P_{1},..,P_{n} \)) =

\begin{enumerate}
\item pick \( P=P_{i} \) with minimum y value.
\item compute \( \theta _{j}=slope(P,P_{j})\forall j\neq i \)
\item sort slopes \( Sort(\theta _{1},...,\theta _{n-1}) \)
\item push \( P_{1},P_{2} \) onto stack C
\item while \( size(C)\geq 2 \) let \( C_{1}=Pop(C),C_{2}=Pop(C) \) if \emph{LR\_test(Line\_segment(\( C_{1},C_{2} \)),\( P_{i} \))=R then \( Pop(C) \) else \( Push(P_{i});i:=i+1 \)}
\item push \( P \) and return C
\end{enumerate}
Heuristically, this algorithm winds counterclockwise around the points, unwinding
to remove points not in the convex hull every time it discovers (by \emph{LR\_test})
that a point is not in the convex hull. The time complexity of this algorithm
is dominated by the sort, \( O(n\log n) \).

\end{document}