Post solution for the in-class exercise to this thread.

Best,

Chris

Name: Amer Rez

*we split the points we have in two groups: (first three, last three) *apply the same on the first group: we get (first two, third point) *apply the same till we end up with 6 groups, each group is a single point.

• the convex hull for each point is the point itself

*Merging is to find the min and max for X and Y for both groups

*Last result Convex hull: Xmin = 0 Xmax = 3 Ymin = -5 Ymax = 5

For all points: draw a line between any two points.check if all other points lie any one side of a line.
if yes: keep this line and increment the coordinate in opposite side of where all other points lie.

Base case: individual points are the base case. Merging: While merging two sub convex hulls, as the points are already sorted by x value, connect the two highest magnitude y valued co-ordinates.

Points (0,0),(1,12),(1,−12),(2,5),(2,−5),(3,0)

Algorithm: Roughly, sort points by x coordinate. Put first half of points in one set, rest in other. Compute convex hulls of the two sub-problems and merge results).

1. sort on x axis

Sorted: (0,0),(1,1/2),(1,−1/2),(2,5),(2,−5),(3,0)

Left half: (0,0),(1,1/2),(1,−1/2) Right half:(2,5),(2,−5),(3,0)

Group ties in x coordinate: Left set: L1 = {(0,0)} L2 = {(1,1/2), (1,-1/2)} Right set: R1 = {(2,5),(2,−5)} R2 = {(3,0)}

order the ties based on y coordinate:

Left set: L1 = {(0,0)} L2a = {(1,1/2), (1,-12)} Right set: R1 = {(2,5),(2,−5)} R2 = {(3,0)}

Merge these: convex holes: (0,0) (1, -1/2) (1, 1/2) (2, -5) (2, 5) (3,0)

Merge 3 points as a triangle: {(0,0), (1,-1/2), (1, 1/2)} and {(2, -5) (2, 5) (3,0)}

Final convex hull: {(0,0), (2, -5) (2, 5) (3,0)}

1. What I did: Take the max/min x and y and check if other points are in the convex hull.

`For the base case when there is a single vertex, include it in the convex hull

`When there are two or points, include them in the convex hull

`For more than three points identify the point with lowest and highest x & y co-ordinates in both hulls.

`Merge the points to obtain the convex hull

Take al possible combinations of points one by one and check for each case, if other points lie on one side of the line. if they do: hold on to this line and increment the coordinate in opposite side of where all other points lie.

• Divide each group until single points are reached in each of the group.
• Merge rules of two groups : Among the two groups being merged, pick points corresponding to minx, miny, maxx and maxy by comparing across both the sets. include these 4 points to the merge results and they correspond to the convex hull of that level.

Example : Merging { (0,0) ,(1,1/2), (1,-1/2) } and {(2,5) ,(2,-5), (3,0) } Min x point is (0,0). Max x point is (3,0). Min y point is (2,-5) and Max y point is (2,5). Result of merge/ Convex hull : {(0,0) ,(2,5), (2,-5) and (3,0)}

Name :Yeshwanth [011431017]