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

-- Sep 27 In-Class Exercise

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

-- Sep 27 In-Class Exercise

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.

-- Sep 27 In-Class Exercise

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.

-- Sep 27 In-Class Exercise

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)} 2. What I did: Take the max/min x and y and check if other points are in the convex hull.

-- Sep 27 In-Class Exercise

@BT@For the base case when there is a single vertex, include it in the convex hull @BT@When there are two or points, include them in the convex hull @BT@For more than three points identify the point with lowest and highest x & y co-ordinates in both hulls. @BT@Merge the points to obtain the convex hull

-- Sep 27 In-Class Exercise

((resource:IMG_4272.JPG|Resource Description for IMG_4272.JPG))

-- Sep 27 In-Class Exercise

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.

-- Sep 27 In-Class Exercise

- 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]

-- Sep 27 In-Class Exercise

((resource:ca.jpeg|Resource Description for ca.jpeg))