$3\mathrm{.}1$ Divide and Conquer Algorithm $3\mathrm{.}1\mathrm{.}1$ Time Complexity Analysis

Algorithm $2$ Divide and Conquer Convex Hull Algorithm

$1$: $2$: $3$: $4$: $5$:

$6$: $7$: $8$: $9$:

$10$:

$11$: $12$: $13$: $14$: $15$:

Input: A set of points P

Output: Convex hull of P

procedure DivideAndConquerHull$($P$)$

if $|$P$|3$ then

Compute the convex hull directly and return it

Sort points by x$-$coordinate

Split P into two subsets PL and PR at the median

$$ Base case

HL $$ DivideAndConquerHull$($PL$)$ HR $$ DivideAndConquerHull$($PR$)$ return MergeHulls$($HL$,$ HR$)$

$$ Recursively find convex hull for left subset $$ Recursively find convex hull for right subset $$ Merge two hulls using upper and lower tangents

procedure MergeHulls$($HL$,$ HR$)$

Find the upper tangent between HL and HR Find the lower tangent between HL and HR Merge the two hulls using the tangents return the merged convex hull

Problem $14.$ Explain the time complexity of the divide and conquer convex hull algorithm. Break down the time complexity for each step, including:

$$ Dividing the points into two subsets,

$$ Recursively solving the convex hull for each subset, and $$ Merging the two convex hulls.

$[10$ marks$]$

Solution.

Problem $15.$ Given the recurrence relation for the divide and conquer convex hull algorithm:

T$($n$)=2$T n $+$ O$($n$)2$

Solve this recurrence relation using the Master Theorem to determine the overall time complexity of the algorithm. $[10$ marks$]$

Solution.

$6$