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