What is a convex hull in data structure?

For a given set of points S in a plane, the convex hull is a line completely enclosing all the points within the plane such that no concavities are left. In other words, the convex hull of a set of points is the smallest convex polygon consisting of all points within the plane.

Usage of the convex hull

The convex hull is widely used in mathematics, statistics, and computational geometry. Some applications of convex hull include:

• With convex cars, detecting the paths to avoid collision is easier. In such cars, a convex hull is used to compute the routes.
• The convex hull property is used to detect intersections of curves such as the Bezier curve, which lies in the convex hull of its control points.
• In ethology, the convex hull is used to study animal behavior. It is used to estimate the home range of an animal depending on the points where the animal has been spotted.

Convex hull can be computed using various algorithms.

Jarvis’ march (gift wrap) algorithm

Jarvis’ march algorithm applies to two-dimensional cases. The algorithm has O(nh) time complexity, where n is the number of points and h is the number of points on the convex hull.

Algorithm

Assume three non-linear points, as shown in the figure above. The Jarvis’ march algorithm can be changed based on linearity. The complete algorithm has to deal with degenerate cases when the convex hull includes 1 or 2 vertices and with the issues involved in computer computations and input data.

1. The algorithm begins with i = 0 and the point P₀ is on the convex hull.
2. It selects point P_{i + 1} such that all the other points are on the right side of the line P_i P_{i + 1}.
3. The point can be located in O(n) time by comparing the polar angles of all the points with respect to point P_i as a center of the polar coordinates.
4. Considering i = i + 1, and repeating till one reaches P_h = P₀ again, generates the convex hull in h steps. 

In 2D, Jarvis’ algorithm is like the process of winding a string around a set of points. This approach can be applied to higher dimensions.

Pseudocode for Jarvis’ wrap algorithm

Input: Number of input points n, number of points on the hull h

Output: Corner points on the convex hull

Steps:

Algorithm jarvis(Q)      // Q is the point set

    pointOnHull = leftmost point in Q   //Which will be part of the convex hull (Q)

    k := 0           //Final set size is k.

    repeat

        P[k] := pointOnHull         //P will be a set of points that will form the convex hull. 

        endpoint := Q[0]      //initial endpoint for an edge on the convex hull

        for m from 0 to |Q| do

            // endpoint == pointOnHull will rarely occur. It can happen only when m == 1 and a better endpoint has not yet been set for the loop

            if (endpoint == pointOnHull) or (Q[m] is on left of line from P[k] to endpoint) then

                endpoint := Q[m]   // found greater left turn, update endpoint

        k := k + 1

        pointOnHull = endpoint

    until endpoint = P[0]      // wrapped around to first hull point

Graham scan algorithm

Graham scan algorithm is used to determine the convex hull of a finite set of points in a plane. It has a time complexity of O(n log n). The algorithm searches all the vertices of the convex hull located on the boundary. This algorithm makes use of a stack to detect and remove concavities across the boundary. Graham’s algorithm is also known as successive local repair.

Algorithm

1. Graham’s algorithm begins with finding the point having the lowest y-coordinate. If such a coordinate exists in more than one point for a given set of points, then the point having the lowest x-coordinate is named P and the step is performed in O(n) time, where n is the number of points
2. Next, the set of points are sorted in increasing order of the angle. The point P and remaining points make an angle with the x-axis. This process can be done using any sorting algorithm like heap sort, having O(n log n) time complexity. (For the sorting, it is not required to compute the angle. Any angle which is monotonic in the interval [0,π ] can be used.)
3. The cosine can be calculated using the dot product or the slope of the line. If there is a numeric position, the comparison function can use the sign of cross product to find the angles in the sorting algorithm. After sorting all the points in the array, the algorithm proceeds with the next step.
4. Now, the algorithm checks if there are two or more points at the same angle.
5. If so, then all the angle points except the one farthest from P are removed to obtain a new array m. If m is less than 3, then a convex hull will not be possible.
6. Otherwise, points P, A, B, and C are pushed to stack S.
7. The process is repeated for the rest (m-3) points until the orientation of the 3 points changes counterclockwise or they take a left turn.
8. Finally, the process will return to the point where it began. The stack will now comprise the points on the convex hull in the counterclockwise order.

Pseudocode for Graham’s scan algorithm

Input: Number of input points n, number of points on the hull h

Output: Corner points on the convex hull

P = number of points

points[P+1] = the array of points

swap points[1] with the point having the lowest y-coordinate

sort points by a polar angle with points[1]  

points[0] = points[P] // These points[0] need to be a sentinel point that stops the loop.

let Q = 1 // Q will denote the number of points on the convex hull.

for i = 2 to P: // Find next valid point on convex hull.

    while counterclockwise(points[Q-1], points[Q], points[k]) <= 0:

        if Q > 1:

            Q -= 1

            continue

        // All points are collinear

        else if k == P:

            break

        else

            k += 1

    Q += 1 // Update Q and swap points[k] to the correct place.

swap points[Q] with points[k] // When Q and k are the same, the algorithm ends up in an infinite loop.

Other convex hull algorithms

Quick hull

Quick hull algorithm is similar to the quicksort algorithm. It has a time complexity of O(n log n), which can degenerate to O(n²) in the worst case.

Kirkpatrick-Seidel algorithm

This is the first optimal output-sensitive algorithm with a time complexity of O(n log h) where n represents the number of input points and h represents the number of points in the convex hull.

Chan’s algorithm

Chan’s algorithm uses Jarvis’ algorithm and an O(n log n) algorithm for determining convex hull.

Context and Applications

The convex hull topic is significant in all courses having data structure as a subject. This includes:

• Bachelors in Computer Applications
• Masters in Computer Applications
• Bachelors of Science in Information Technology
• Masters of Science in Information Technology

Practice Problems

Q1. What is the average-case time complexity of a quick hull algorithm?

1. O(N)
2. O(N log N)
3. O(2N)
4. O(log N)

Answer: Option b

Explanation: The average time complexity of the quick hull algorithm uses the divide and conquer technique. Hence, the time complexity, in this case, will be O(n log n).

Q2. What will be the time taken to identify n points lying in a convex quadrilateral?

1. O(N)
2. O(N log N)
3. O(2N)
4. O(log N)

Answer: Option a

Explanation: Computationally, the time required to determine the n points within a convex quadrilateral is O(n).

Q3. What is the Jarvis’ march algorithm also called?

1. Gift wrapping
2. Extreme points mapping
3. Line segment linking
4. Non-convex region mapping

Answer: Option a

Explanation: The Jarvis’ march algorithm is also known as the gift wrapping algorithm or Jarvis’ gift wrapping algorithm.

Q4. Which of the following is an application area of Graham's scan algorithm?

1. Numerical problem
2. Computational geometry
3. Image processing
4. Vertex problem

Answer: Option b

Explanation: Graham’s scan algorithm is used for determining the convex hull, which is a computational geometry concept. So, Graham’s scan algorithm is an example of computational geometry algorithms.

Q5. To which of the following is the quick hull algorithm similar?

1. Quicksort
2. Merge sort
3. Linear sort
4. Shell sort

Answer: Option a

Explanation: As per the average and worst-case time complexities, the quick hull algorithm is similar to the quicksort algorithm in the data structure.

Common Mistakes

• The algorithm and applications of the convex hull are different for different cases (finite points set, simple polygon). So, students need to consider the special cases while identifying the convex hull for different shapes.
• When there are three collinear points, the algorithm might not work correctly.

Related Concepts

• Orthogonal convex hull
• Convexity
• Convex hull in image processing
• Other types of structures (relative convex hull, conical hull, and so on.