This is a dynamic demo of Chan's Algorithm, an optimal, output-sensitive algorithm for computing the convex hull of a point set in O(nlogh) time.

n is the number of input points and h is the number of output hull points.

Hit the space bar or use the buttons below to walk through the steps of the algorithm.

Additional resources:
       Chan's original paper
       Video walkthrough
       Python implementation
       Mathematical explanation
       Convex hulls pseudocode
       Visualizing algorithms
       Demo source code
       D3.js Velocity.js Less.js

First, let's add some points to our plane. You can click to the left to add your own points or press P to add random points.

In the next few steps we will be grouping our point set into smaller convex hulls and then finding the convex hull of those smaller hulls.

Hit the space bar when you are ready to continue.

Now that we have our points, we pick some small constant m. The choice of m will be explained later in the demo.

We partition our point set into groups of m points.

In this example m is set to 5 and each color represents a group of m points.

Given these groups of m points, we find the convex hull of each group with an O(nlogn) algorithm. In this demo we use Graham Scan.

Because each group has size m we can convex hull each group in O(mlogm). There are O(n/m) groups.

In total this step takes O(nlogm) time.

We then use Gift wrapping, an O(nh) algorithm on the small convex hulls.

To use gift wrapping on convex hulls rather than points we can perform a binary search to determine the tangent between an extreme point and a convex hull. A binary search on a small convex hull takes O(logm).

We can compute tangents for all O(n/m) groups in O(n/m * logm) time. We use the tangent with the largest angle. By doing this we get one edge of the overall convex hull. We must do this for all h hull points.

We can assume for now that m < h so this step is O(nlogh) like the last step.

We have to be careful that we do not exceed h iterations of gift wrapping given our O(n/m) input size. Therefore, we halt gift wrapping execution after m iterations.

We want to increase m until it equals h. If we increase m too slowly our gift wrapping time overall will surpass O(nlogh). On the other hand, if we increase m too quickly some gift wrapping iteration will take much more than O(nlogh) on its own.

To solve this problem we can utilize a double exponential. We let m = 2^2t where t is the current iteration number.

We throw away the work we do in each attempt at finding an m equal to h. Because iterations form a geometric series the total work is still O(nlogh).

We now have the convex hull of our orignal point set.

Press restart to try it again!