1.  Merge Convex hull

1. Sort P₁,...,P_n by the X value

1. H₁ = MCE( P₁,...,P_n/2 ), H₂ = MCE( P_n/2+1,...,P_n )

2. Merge Hull( H₁,H₂ )

1.1  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.

1.2  Upper Merge Hull

Merge upper hull( H₁,H₂ ) = start with the inner (x value near the median point) points, throwing out those with a y value lower than the maximum.

1.3  Timing analysis

T(n) = 2T(n/2)+c(h₁+h₂) which implies T(n) = O(nlg(n))

2.  Quick Hull

QUH( l,P = {P₁,...,P_n},r ) =

1. find highest point (large y value) m from line (l,r)

2. remove all points below line (l,r)

3. QUH( l,P,m ),QUH( m,P,r )

2.1  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) = W(cn²)

2.2  average case

The average case is points distributed uniformly throughout a semicircle. It will have time complexity of about: T(n) = T(n₁)+T(n₂)+cn for n₁+n₂ £ an with a < 1 .

3.  The ultimate 2d convex hull

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

Upper Hull( l,P,r )

1. using median partition P into P_L,P_R based on the x value

2. Find Bridge b = (a,b) in upper hull from P_L,P_R

3. Remove points below the line segments defined by (l,a,b,r) from P_L,P_R

4. return Upper Hull( l,P_L,a ), Upper Hull( b,P_R,r )

3.1  Timing

let h = # edges on hull

The time complexity is c*n*lg₂(h) .

Check this by plugging it into the time complexity equation.

T(n,h) = T(n/2,h₁)+T(n/2,h₂)+cn £ c*n/2*(lg₂h₁+lg₂h₂)+c*n

£ c*n/2*lg₂(h²/4)+cn = c*n*lg₂(n)

3.2  finding the bridge

1. form n/2 pars of points from P and compute their slopes.

2. Find median slope, S.

3. Find support line, SL, with slope S.

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

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

6. Else if SL has the ``right'' slope you are done

3.2.1 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