A set S in a vector space is convex if$,$ for any two points x$,$ y in S$,$ the line segment joining x and y is entirely contained within S$.$ Formally, S is convex if for all x$,$y in S and in $[0,1],$ the point x $+(1$ $)$y in S$.$

For example the set X shown below is convex because you can take any two points in the set and join a straight line between them such that all points on the line belong to the set X$,$ Set Y is not convex because the line joining points A and B have some points that are not contained within the set Y $.$Problem $1.$ Identify Convex and non Convex set from the following illustrations. $[2$ marks$]2\mathrm{.}1$ Definition of Convex Hull

Definition $1.$ The smallest convex set refers to the minimal convex boundary that encloses all the points, meaning there is no other convex set with a smaller area $($or volume in higher dimensions$)$ that still contains all the points.Figure $3$: If we needed to find the convex hull for the points given above, simply joining the points one by one does not suffice as the line joining the two points shown in purple lies entirely outside the set and hence the above boundary of the points doesnt represent a convex hull

Problem $2.$ Show that the convex hull of a finite set of points $($more than two points$)$ is a convex polygon. You can assume that the points are non$-$collinear. $[5$ marks$]$

Solution.Problem $3.$ Find the convex hull of the set of points $\{(0,0),(1,1),(2,2),(1,0),(2,1)\}.$ Do this by drawing the convex hull for this point set. $[3$ marks$]$

Solution.

$2\mathrm{.}2$ Properties of Convex Hull $2\mathrm{.}2\mathrm{.}1$ Minimality

Problem $4.$ Prove that the convex hull of a set of points is minimal. $[3$ marks$]$ Solution.

$2\mathrm{.}2\mathrm{.}2$ Intersection Property

Problem $5.$ Prove that the convex hull is the intersection of all convex sets containing a given set. $[3$ marks$]$

Solution.

$2\mathrm{.}2\mathrm{.}3$ Uniqueness

Problem $6.$ Prove that the convex hull of a set of points is unique. $[3$ marks$]$ Solution.

$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 $\{(0,0),(1,1),(2,2),(1,0),(2,1)\}$ 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$]$

$3$

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

$1$: $2$: $3$: $4$: $5$: $6$: $7$: $8$: $9$:

$10$: $11$: $12$:

$13$: $14$: $15$: $16$: $17$: $18$: $19$:

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$)$

upperT angent $$ FindUpperTangent$($Hull A$,$ Hull B$)$ lowerT angent $$ 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 $(1,1),(2,3),(3,2),(5,4),(6,1),$ and $(7,3),$ find the upper and lower tangents between the convex hulls of the sets $\{(1,1),(2,3),(3,2)\}$ and $\{(5,4),(6,1),(7,3)\}.$ For finding the lower tangent, use the algorithm you wrote for the previous question. $[10$ marks$]$

Solution.

Problem $11.$ Merge the convex hulls $\{(0,0),(1,0),(1,1)\}$ and $\{(2,1),(2,2)\}$ 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 O$($n$)$ time.

$[3$ marks$]$

Solution.