1.  Sorting vs. Convex hull

1.1  sorting algorithms

A lower bound on the time complexity of sorting algorithms given only the use of a compare primitive, compare(a,b), which returns (a < b) is W(log₂n!) » W(nlog₂n) . You can see this by noting that there are n! possible outcomes to sorting n elements which implies that log₂n! choices must be made.

1.1.1 Insertion sort

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

1.1.2 heap sort

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

1.1.3 merge sort

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

1.1.4 median sort

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.

Otherwise known as quicksort.

let QSort(P) =

m = Random(P)

return Sort({P_i:P_i < m}) :m: Sort({P_i:P_i > m})

1.2  Convex hull algorithms

1.2.1 The primitive operations of convex hull algorithms

• testing if 2 line segments intersect, bool Intersect(Line_segment_1,Line_segment_2)
• testing if a point lies to the left or to the right the line derived from a line segment, LR_test(Line_segment,Point) =

  Sign(Det([

  LS11	LS12	1
  LS21	LS22	1
  P31	P32	1

  ] )) 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, Point lies to the left of the line defined by the line segment

1.2.2 definitions

• A Í R² is a set in the plane
• CH(A) = simplest convex set conatining A
• A Í R² is convex if forall "p₁,p₂ Î AÞ LineSegment(P₁,P₂) Í A

1.2.3 Convex hull heap sort analog = Graham scan

Graham Scan( P₁,..,P_n ) =

1. pick P = P_i with minimum y value.
2. compute q_j = slope(P,P_j)"j ¹ i
3. sort slopes Sort(q₁,...,q_n-1)
4. push P₁,P₂ onto stack C
5. while size(C) ³ 2 let C₁ = Pop(C),C₂ = Pop(C) if LR_test(Line_segment( C₁,C₂ ), P_i )=R then Pop(C) else Push(P_i);i: = i+1
6. push P and return C

Heuristically, this algorithm winds counterclockwise around the points, unwinding to remove points not in the convex hull every time it discovers (by LR_test) that a point is not in the convex hull. The time complexity of this algorithm is dominated by the sort, O(nlogn) .