Incremental algorithm

The incremental algorithm is an algorithm for computing the convex hull of a set of points in two or more dimensions.

The basic idea is to add points one at a time updating the hull as we proceed.

Two dimensions

expand Sorry, but you need Java to see the animation. If the new point (shown in red) is inside the hull there is nothing to do. Otherwise, we must delete all the edges (shown in yellow) that the new point can see.
expand Sorry, but you need Java to see the animation. Add two edges to connect the new point to the remainder of the old hull.
expand Sorry, but you need Java to see the animation. Repeat for the next point outside the hull.

If we use a data structure for the hull that allows us to get from one edge to an adjacent edge in constant time, then we can find one visible edge in linear time and and all the others in constant time per edge. The update takes linear time and the total time is O(n^2).

Three dimensions

You can use the left mouse button to look at any of the images below from a different direction.
expand Sorry, but you need Java to see the animation. If the new point is inside the hull there is nothing to do. Otherwise, we must delete all the faces (shown in yellow) that the new point can see.
expand Sorry, but you need Java to see the animation. Add a pyramid of faces to connect the new point to the remainder of the old hull.
expand Sorry, but you need Java to see the animation. Repeat for the next point outside the hull.

More dimensions

We can generalise this to any number of dimensions.
lambert@cse.unsw.edu.au
Last modified: Tue Sep 22 16:53:01 AET 1998