$3$ Divide and Conquer Approach for Convex Hull

$3\mathrm{.}0\mathrm{.}1$ Splitting the Set of Points

Problem $7.$ Split a given set of points $\backslash (\backslash \{(0,0),(1,1),(2,2),(1,0),(2,1)\backslash \}\backslash )$ into two subsets by a vertical line. Some considerations when you are splitting:

$1.$ Avoid Collinearity: Ensure the line doesn't overlap any points you want to separate.

$2.$ Subset Sizes: Decide if you want equal$-$sized subsets or if different sizes are acceptable.

$3.$ Boundary Conditions: Determine whether points on the line belong to the left or right subset.

$[5$ marks$]$

Solution.

Problem $8.$ Why is it necessary to divide the points with respect to the median and not the mean? $[4$ marks$]$

Solution.

$3\mathrm{.}0\mathrm{.}2$ Merging the Convex Hulls

Definition $2($The Upper Tangent$).$ The upper tangent between two convex hulls is the line segment that touches both hulls at exactly one point each and lies above all other points in both hulls.

Definition $3($The Lower Tangent$).$ Similarly, the lower tangent is the line segment that touches both hulls at exactly one point each and lies below all other points in both hulls.

Problem $9.$ Given the following code to merge convex hulls including the code for the upper tangent, write the code finding the lower tangent. $[8$ marks$]```$

Algorithm $1$ Convex Hull Merging Process

Input: Two convex hulls, Hull$\_$A and Hull$\_$B

Output: Merged convex hull

procedure FindUppertangent$($Hull$\_$A$,$ Hull$\_$B$)$

Set i $=$ index of the rightmost point of Hull$\_$A

Set j $=$ index of the leftmost point of Hull$\_$B

while line segment $($Hull$\_$A$[$i$],$Hull$\_$B$[$j$])$ is not an upper tangent do

if not an upper tangent for Hull$\_$A then

Move i counterclockwise in Hull$\_$A

else if not an upper tangent for Hull$\_$B then

Move j clockwise in Hull$\_$B

return $($Hull$\_$A$[$i$],$Hull$\_$B$[$j$])$ as the upper tangent

procedure FindLOWERTANgEnt$($Hull$\_$A$,$ Hull$\_$B$)$

procedure MErgeHulls$($Hull$\_$A$,$ Hull$\_$B$)$

upperTangent $\backslash$leftarrow FindUpPERTAngEnT$($Hull$\_$A$,$ Hull$\_$B$)$

lowerTangent $\}\backslash$leftarrow$\backslash$mathrm$\{$ FindLOWERTAngEnt$($Hull$\_$A$,$ Hull$\_$B$)$

Initialize an empty list for the merged hull

Traverse points from upperTangent to lowerTangent on Hull$\_$A

Traverse points from upperTangent to lowerTangent on Hull$\_$B

return the merged convex hull

$```$

Solution.

Problem $10.$ Given the points $\backslash ((1,1),(2,3),(3,2),(5,4),(6,1)\backslash ),$ and $\backslash ((7,3)\backslash ),$ find the upper and lower tangents between the convex hulls of the sets $\backslash (\backslash \{(1,1),(2,3),(3,2)\backslash \}\backslash )$ and $\backslash (\backslash \{(5,4),(6,1),(7,3)\backslash \}\backslash ).$ For finding the lower tangent, use the algorithm you wrote for the previous question. $[10$ marks$]$

Solution.

Problem $11.$ Merge the convex hulls $\backslash (\backslash \{(0,0),(1,0),(1,1)\backslash \}\backslash )$ and $\backslash (\backslash \{(2,1),(2,2)\backslash \}\backslash )$ using the algorithm mentioned above. $[10$ marks$]$

Solution.

Problem $12.$ Why not select the highest point for the upper tangent and the lowest points for the lower tangent? Why use the mentioned algorithm? $[5$ marks$]$

Solution.

Problem $13.$ Explain why the merging step in the divide and conquer algorithm takes $\backslash ($ O$($n$)\backslash )$ time. $[3$ marks$]$

Solution. $3\mathrm{.}1$ Divide and Conquer Algorithm

$3\mathrm{.}1\mathrm{.}1$ Time Complexity Analysis

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:

$\backslash [$

T$($n$)=2$ T$\backslash$left$(\backslash$frac$\{$n$\}\{2\}\backslash$right$)+$O$($n$)$

$\backslash ]$

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

Solution.