-- Sep 22 In-Class Exercise

((resource:3. Convex Hull.jpg|Resource Description for 3. Convex Hull.jpg))

-- Sep 22 In-Class Exercise

((resource:615235d5d658d755e464e3b9.png|Resource Description for 615235d5d658d755e464e3b9.png))

-- Sep 22 In-Class Exercise

  (4,0) as a group

((resource:tempsnip.png|Resource Description for tempsnip.png)) We find the convex hull for the given points using the Divide and conquer method. - We divide the points based on similar X coordinates. - We get (0,0) as a group, (1,-0.5) and (1,0.5) as a group, (3,5) and (3,-5) as a group, (4,0) as a group - We start finding convex hulls for closer groups - (0,0) and (1,-0.5) and (1,0.5) form a triangle as shown in the figure - (4,0) and (3,5) and (3,-5) form a triangle as shown - We then take a line from extremes of both the triangles and rotate them so as to include the other points. - We finally end up with a convex hull including all the points as shown in the figure.

-- Sep 22 In-Class Exercise

Using the Divide and Conquer method we find the convex hull for the given points: Initially sort the points using the x-coordinates and split them into 2 halves. Find the convex hull for the first and the second half separately We get 2 triangles as shown in the figure. Merge these 2 triangles using their y-coordinate extremes, then we get the polygon as shown. The line has to be rotated along the coordinate (3,5) and is rotated clockwise so that (0,0) coordinate is included. Similarly, the line through (3.-5) is rotated along the coordinate and is rotated anticlockwise so that (0,0) coordinate is included. We finally get the convex hull which includes all the given points. ((resource:InkedIMG-6476_LI.jpg|Resource Description for InkedIMG-6476_LI.jpg))

-- Sep 22 In-Class Exercise

We can find convex hull of data points using '''divide and conquer''' approach. We sort the points according to their x-coordinate, find convex hulls of each set of points and merge the results to get the convex hull of all points. Given: Points (0,0), (1,0.5), (1/-0.5), (3,5), (3,-5) and (4,0) Splitting them based on x-coordinates, we get 4 sets: {0,0}, {(1,0.5),(1,-0.5)}, {(3,5), (3,-5)} and {4,0} Now, to merge them back together, we look through the set of points to find minimal and maximal y-values From sets {(1,0.5),(1,-0.5)} and {(3,5), (3,-5)}, we connect the maximal y-values from points (1,0.5) and (3,5). Then we connect to point (0,0) and see find cross-product of the edges to check the direction of movement to find the next point. We have to move clockwise and so we disregard the edge from (3,5) to(1,0.5) and instead use the line from (3,5) to (0,0) as an edge of the convex hull. Similarly, for minimal y-value case, we connect points (3,-5) to (1,-0.5) and (0,0) and realize we need to move anti-clockwise and so we eliminate the edge involving the former point. In the same way, we connect (4,0) to the set {(3,5), (3,-5)} This gives us the convex hull with points (0,0), (3,5), (4,0) and (3,-5) ((resource:AI.jpeg|Resource Description for AI.jpeg))

-- Sep 22 In-Class Exercise

1.We will first the sort the pairs of co-ordinates according to the x-coordinate 2. Then we will put the 1st 3 pairs in set 1 and the remaining 3 in set 2. 3. Set 1 = (0,0),(1, 1/2), (1, -1/2) 4. Set 2 = (3, 5), (3, -5), (4, 0) 5. Set 1 forms a triangle on the left and set 2 forms a triangle on the right. 6. Now we need to merge these 2 triangles 7. For that we will consider (3, 5) and (1, 1/2). The dot product of these 2 is positive and will move in a clockwise direction and connect to (0, 0). 8. Similarly the vector connecting (3, -5) and (1, -1/2) will move outward in an anti-clockwise direction and connect to (0, 0). ((resource:sept 22.jpeg|Resource Description for sept 22.jpeg))