Convex Hull and Searching

The Convex Hull is the line completely enclosing a set of points in a plane so that there are no concavities in the line. More formally, we can describe it as the smallest convex polygon that encloses a set of points such that each point in the set lies within the polygon or on its perimeter.

Algorithm

Graham Scan Algorithm:

Using Graham’s scan algorithm, we can find Convex Hull in O(nLogn) time.

Algorithm:

1) Find the bottom-most point by comparing y coordinate of all points. If there are two points with the same y value, then the point with smaller x coordinate value is considered. Let the bottom-most point be P0. Put P0 at first position in the output hull.

2) Consider the remaining n-1 points and sort them by polar angle in counterclockwise order around points[0]. If the polar angle of two points is the same, then put the nearest point first.

3 After sorting, check if two or more points have the same angle. If two more points have the same angle, then remove all same angle points except the point farthest from P0. Let the size of the new array be m.

4) If m is less than 3, return (Convex Hull not possible)

5) Create an empty stack ‘S’ and push points[0], points[1] and points[2] to S.

6) Process remaining m-3 points one by one. Do following for every point ‘points[i]’

        4.1) Keep removing points from the stack while orientation of following 3 points is not counterclockwise (or they don’t make a left turn).

            a) Point next to top in stack

            b) Point at the top of stack

            c) points[i]

         4.2) Push points[i] to S

5) Print contents of S

Time Complexity:

The merging of the left and the right convex hulls take O(n) time and as we are dividing the points into two equal parts, so the time complexity of the above algorithm is O(n * log n).

Graham's scan has these steps:

1. Find p0, the point with the minimum y coordinate,

2. Sort all the remaining points in order of their polar angle from p0

3. Initialize a stack, S

4. push(S,p0)

5. push(S,p1)

6. push(S,p2)

7. for i=3 to n do
   while (angle formed by top next(S), top(S) and pi makes a right turn
   

• pop(S)
• push(S,pi)

8. return S

This algorithm takes O(n logn) time.

A second algorithm, known as Jarvis' march proceeds as follows:

• Find the 'left-most' (minimum x) and 'right-most' (maximum x) points.
• Divide points into those above and below the line joining these points.
• In the bottom half, starting with the left-most point, add the point with the least angle to the -y axis from the current point until the right-most point is reached,
• Repeat the scan in the upper half.

This algorithm takes O(n h) time, where h is the numer of vertices in the convex hull.

Applications. Among oldest and most well-studied problems in computational geometry problems.

• Robot motion planning.
• Shortest perimeter fence enclosing P.
• Smallest area polygon enclosing P.
• Unique convex polygon whose vertices are points in P that encloses P.
• Smallest convex set containing all N points (i.e., intersection of all convex sets containing the N points).