-- Sep 22 In-Class Exercise
Algorithm ->
1. Roughly, sort the points by their x coordinate.
2. Put first half of the points in one set, the rest in the other.
3. Compute convex hulls of the two sub-problems and merge results.
Base case-> Individual points in each set will form the base case.
1. Sorting based on x coordinate - Two sets of three points each will form set 1 and set 2. Set 1 consists of {(0,0), (1, Β½), (1,-1/2)} and set 2 consists of {(3,5) ,(3,-5), (4,0)}.
2. After recursive splitting of set 1 and 2, we will have (0,0), (1,1/2), (1,-1/2), (3,5), (3,-5), (4,0).
Merging -> As the points are sorted according to x coordinate value, consider the maximum and minimum y coordinate values for merging.
1. First merging will result in 4 sets which are set 1 {(0,0)}, set 2 {(1,1/2), (1,-1/2)} , set 3 {(3,5) , (3,-5)} and set 4 {(4,0)}.
2. Set 1 and 2 will merge to form the left triangle and set 3 and 4 will merge to form the right triangle.
3. For connecting the points from right triangle to the left triangle, first consider (3,5) and (1,1/2). The vector that connects these two points will move outward in clockwise direction (as determined by the cross product) and connect to (0,0).
4. Similarly, the vector that connects (3,-5) and (1,-1/2) will move outward in anticlockwise direction to connect to (0,0).
Finally, the points (0,0), (3,5), (3,-5) and (4,0) form the convex hull.
(
Edited: 2021-09-22)
<u>Algorithm</u> ->
1. Roughly, sort the points by their x coordinate.
2. Put first half of the points in one set, the rest in the other.
3. Compute convex hulls of the two sub-problems and merge results.
<br>
<u>Base case</u>-> Individual points in each set will form the base case.
1. Sorting based on x coordinate - Two sets of three points each will form set 1 and set 2. Set 1 consists of {(0,0), (1, Β½), (1,-1/2)} and set 2 consists of {(3,5) ,(3,-5), (4,0)}.
2. After recursive splitting of set 1 and 2, we will have (0,0), (1,1/2), (1,-1/2), (3,5), (3,-5), (4,0).
<br>
<u>Merging</u> -> As the points are sorted according to x coordinate value, consider the maximum and minimum y coordinate values for merging.
1. First merging will result in 4 sets which are set 1 {(0,0)}, set 2 {(1,1/2), (1,-1/2)} , set 3 {(3,5) , (3,-5)} and set 4 {(4,0)}.
2. Set 1 and 2 will merge to form the left triangle and set 3 and 4 will merge to form the right triangle.
3. For connecting the points from right triangle to the left triangle, first consider (3,5) and (1,1/2). The vector that connects these two points will move outward in clockwise direction (as determined by the cross product) and connect to (0,0).
4. Similarly, the vector that connects (3,-5) and (1,-1/2) will move outward in anticlockwise direction to connect to (0,0).
<br>
Finally, the points (0,0), (3,5), (3,-5) and (4,0) form the convex hull.