Convex Hull (Graham’s Scan Algorithm)

The Convex Hull is a fundamental algorithm used in computational geometry. It is used to find the smallest convex polygon that contains all the given points in a plane. Convex Hull is widely used in various fields such as computer graphics, pattern recognition, image processing, robotics, and geographic information systems.

History and Development

The Convex Hull problem has been studied by mathematicians for centuries. The first algorithm for finding the Convex Hull was proposed by Jarvis in 1973. The algorithm is known as Jarvis’s march or the gift wrapping algorithm. The runtime of Jarvis’s march is O(nh), where n is the number of points in the input and h is the number of points in the Convex Hull. In 1972, Preparata and Hong proposed an algorithm with a better runtime of O(nlogn). This algorithm is known as the quick hull algorithm. Later, in 1972, Graham proposed an efficient algorithm with an O(nlogn) runtime that is now known as Graham’s scan algorithm.

Purpose and Usage

The primary purpose of the Convex Hull algorithm is to find the smallest convex polygon that contains all the given points in a plane. The Convex Hull can be used to determine the shape of an object, detect the outline of a group of points, and calculate the area and perimeter of a polygon. It is also used in collision detection, path-finding, and rendering in computer graphics.

Key Concepts and Principles

The Convex Hull algorithm works by iterating over all the points and building the convex hull incrementally. The algorithm starts by finding the point with the lowest y-coordinate. If there are multiple points with the same y-coordinate, the point with the lowest x-coordinate is chosen. This point is called the pivot. The algorithm then sorts the remaining points by their polar angle with respect to the pivot.

Once the points are sorted, the algorithm iterates over each point and checks if it belongs to the Convex Hull. If the point is not a part of the Convex Hull, it is discarded, and the algorithm moves to the next point. If the point is a part of the Convex Hull, it is added to the hull. The algorithm then removes any points that are no longer a part of the Convex Hull.

The Convex Hull algorithm uses the following key concepts:

1. Polar Angle: The angle between the line connecting the pivot and a point and the x-axis. This angle is used to sort the points in the input.

2. Pivot: The point with the lowest y-coordinate. If there are multiple points with the same y-coordinate, the point with the lowest x-coordinate is chosen.

3. Convex Hull: The smallest convex polygon that contains all the given points in a plane.

Pseudocode and Implementation

The following pseudocode demonstrates the Convex Hull algorithm using Graham’s scan:

function convexHull(points):
    let pivot = point with the lowest y-coordinate
    sort points by polar angle with respect to the pivot
    let stack = [pivot]
    for each point in points:
        while len(stack) > 1 and orientation(stack[-2], stack[-1], point) <= 0:
            stack.pop()
        stack.append(point)
    return stack

The orientation function checks the orientation of three points in the plane. Given three points a, b, and c, the function returns:

1. Positive value if a, b, and c are in counter-clockwise order.
2. Negative value if a, b, and c are in clockwise order.
3. Zero if a, b, and c are collinear.

The complexity of Graham’s scan algorithm is O(nlogn), where n is the number of points in the input.

Examples and Use Cases

Let us consider an example to understand the Convex Hull algorithm. Given a set of points:

[(0, 0), (0, 5), (1, 1), (2, 2), (3, 1), (4, 2), (5, 0), (5, 5)]

The Convex Hull algorithm will find the smallest convex polygon that contains all the given points. The Convex Hull of the above set of points is:

[(0, 0), (0, 5), (5, 5), (5, 0)]

The Convex Hull can be used to determine the shape of an object, detect the outline of a group of points, and calculate the area and perimeter of a polygon. It is also used in collision detection, path-finding, and rendering in computer graphics.

Advantages and Disadvantages

The Convex Hull algorithm has the following advantages:

1. It is easy to implement.
2. It has a runtime of O(nlogn), which is efficient for practical purposes.
3. It can handle duplicate points and collinear points.

The Convex Hull algorithm also has the following disadvantages:

1. It does not work in the presence of holes in the input.
2. It does not work for non-convex polygons.
3. It is sensitive to the choice of pivot, which can affect the runtime.

Related Algorithms or Variations

There are several variations of the Convex Hull algorithm. Some of them are:

1. Jarvis’s march algorithm: Also known as the gift wrapping algorithm, it has a runtime of O(nh), where n is the number of points in the input and h is the number of points in the Convex Hull.

2. Quick hull algorithm: It has a runtime of O(nlogn) and works by recursively dividing the points into two sets and finding the convex hull of each set.

3. Chan’s algorithm: It has a runtime of O(nlogh) and combines the ideas of Jarvis’s march and quick hull to find the Convex Hull.

4. Incremental algorithm: It works by adding one point at a time and updating the Convex Hull incrementally.

5. Divide and conquer algorithm: It works by recursively dividing the points into smaller subsets and finding the Convex Hull of each subset.

6. Monotone chain algorithm: It works by sorting the points by their x-coordinate and constructing the upper and lower hulls separately.