Convex Hull

What is a convex hull?

In geometry a convex hull, also known as a convex envelope, of a set of points is the smallest convex set that contains it. For a set of points on a 2D plane this can be thought of as the hull that is created by a rubber band that stretches around it.

There are many uses of convex hulls in mathematics however I am personally interested in their use in computational simulations. If a convex hull of a set of points can be generated then that set of points can be meshed knowing that the entire problem space has been covered. This can then lead on to any number of finite element methods used to simulate real world physics.

Jarvis March

Runtime: O(nh) (n - total number of points, h - number of hull points)

Jarvis march is the name of a convex hull generation algorithm known as the gift wrapping algorithm in the special case that the set of points is on a 2D plane. It was published by R. A. Jarvis in Information Processing letters in December 1972.

Starting from a leftmost point of the data set, we keep the points in the convex hull by anti-clockwise rotation. From a current point, we can choose the next point by checking the orientations of those points from the current point. When the angle is largest, the point is chosen. After completing all points, when the next point is the start point, stop the algorithm.

Divide and Conquer

Runtime: O(nh log_p nh) (n - total number of points, h - number of hull points, p - number of recursive partitions)

Divide and conquer is an algorithm design concept which is based in multiple branch recursion. A problem is broken down into smaller and smaller problems which can be solved directly and the answers combined to solve the original problem. In the convex hull generation problem the basic element would be three points making a triangle. The solution used however does not go use that many recursive steps. In actuality this was solved iteratively for the sake of improving the ease of animation but this can be done in parallel on multiple processors with limited memory sharing.

In this example the points are sorted and then separated equally into three subsets. These subsets are individually processed and the convex hull is generated for each using the gift wrapping algorithm. The three convex hulls are then combined to form a new set of points for which the final convex hull will be computed. It is important to note that whilst the points are sorted for visual clarity this is not necessary and even if the convex hulls for the subsets overlap the merge will still work successfully.

Monotone Chain

Runtime: O(n log n) (n - total number of points)

The Monotone Chain algorithm is another method of creating a convex hull from a set of points in a 2d plane. It was developed by A. M. Andrew and published in Information Processing Letters at the end of April 1979 and was revised later on in the year.

First the points are sorted by x coordinate and in case of a tie by y coordinate. First the upper hull is generated starting at the left most point travelling in a clockwise manner and is finished at the right most point. Each subsequent point is chosen by comparing the orientations of every point from the current point. When the angle is largest, the point is chosen. This is duplicated for the lower hull and then the two hulls are combined to create the final convex hull.

It should be noted that this can be partially simplified when calculating the lower hull by removing all points in the upper hull from comparisons except for the left most point. This differs from the divide and conquer method due to the fact that every point is in consideration for both the upper and lower hull, the problem space has not been reduced to a simpler problem.

Graham Scan

Runtime: O(n log n) (n - total number of points)

The Graham Scan algorithm, like the monotone chain algorithm, is a convex hull generation algorithm that has a time complexity faster than the gift wrapping algorithm as it does not depend on the number of hull points, this is true as long as the number of hull points is more than logn for the gift wrapping algorithm. It is also limited to a 2D plane. It is named after Ronald Graham who published the algorithm in Information Processing Letters in January 1972.

First the lowest point in the set is found, if there are two then the leftmost point is used. Next the points are sorted with respect to the angle that they make between the lowest point and the x axis. For each point the previous two points are checked to see if they are going in a clock wise or counter clockwise direction. If the turn is deemed to be clockwise then the second to last point is not in the convex hull and it is rejected. The current point keeps checking the previous points until it reaches a counter clockwise turn, when this happens the current point is added to the convex hull and the algorithm moves on to the next point. This continues until the algorithm reaches the point at which it started.