%% This LaTeX-file was created by <jl> Wed Jan 21 16:47:09 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}

day4 1/21/98

Qoute of the day: ``Someone has to pay.''


\section{2D incremental Convex hull}


\subsection{Inductive assumption:}

The Polygon is convex and has a set of remaining points partitioned by each
edge.

Let \( P=\{P_{1},...,P_{n}\}\subset R^{2} \)


\subsection{Algorithm}

\begin{enumerate}
\item Extract 3 points from P and form a triangle, T. Pick \( C\in T \)

\item Draw a line segment for C to every point in P.

\item Partition P by which edge of T the line segment from C crosses.

\item While there exists point, P, above an edge, E, \emph{BuildTent(P,e,Polygon)}

\end{enumerate}
BuildTent(P,e,Polygon)

\begin{enumerate}
\item Remove all edges from the polygon visible by P.

\item Construct a larger polygon from the nonvisible edges in the Polygon + edges
connecting to P.

\item associate points external to the polygon with the new edgeset of the polygon

\end{enumerate}

\subsection{Timing analysis}

All the work occurs in the BuildTent routine.

In step 1, finding the visible edges will not be too costly because all the
edges of all the polygons will form a planar graph. From euler's formula, if
\( |v|=n \) and \( |E|=m \) then \( m\leq 3n \)

The total cost of step 3 is the number of times that you must check whether
a line segment between \( P_{i} \) and \( C \).

To analyze step 3, run the algorithm backwards.

\begin{itemize}
\item At T(n), Poly = convexhull(\( P_{1},...,P_{n} \))

\item T(n-1) = T(n) - the comparisons necessary to insert \( P_{n} \) into the polygon.

\item The cost to extract a node p on the hull = \# of intersections on left and right
edges of P

\item At a particular point in time. \( |P|=K \)

\item \( \sum _{p\in P}ExtractCost(P)=2*\#intersections\leq 2n \)

\item \( E(ExtractCost)\leq 2n/k \)

\item \( E(\#intersections)\leq \sum _{k=n}^{1}2n/k=2n*\sum _{k=1}^{n}1/k=O(n*log_{2}(n) \) 

\end{itemize}

\section{Linear Programming}


\paragraph{input: collection of constraints: \protect\( A_{ij}x_{j}\leq b\protect \), objective vector \protect\( c\protect \)}


\paragraph{output: \protect\( Min_{c^{T}x}(A_{ij}x_{j}\leq b)\protect \)}

After rotation, the problem is finding the point (x,y) which minimizes the y
value.

Constraints can all be written in one of the forms:

\begin{enumerate}
\item \( H^{+}=\{i:y\geq \alpha _{i}x+\beta _{i}\} \) = constraints on the minimum value of y

\item \( H^{-}=\{i:y\leq \alpha _{i}x+\beta _{i}\} \) = constraints on the maximum value of y

\item \( H^{0}=\{i:\alpha _{i}x\leq \beta _{i}\} \) = vertical constraints

\end{enumerate}
\end{document}