Divide and Conquer algorithm

The divide-and-conquer algorithm is an algorithm for computing the convex hull of a set of points in two or more dimensions.

Two dimensions

First sort the points by x coordinate.


	Sorry, but you need Java to see the animation.	Divide the points into two equal sized sets L and R such that all points of L are to the left of the most leftmost points in R. Recursively find the convex hull of L (shown in light blue) and R (shown in purple).
	Sorry, but you need Java to see the animation.	To merge the left hull and the right hull it is necessary to find the two red edges shown on the left (the upper and lower common tangents). The upper common tangent can be found in linear time by scanning around the left hull in a clockwise direction and around the right hull in an anti-clockwise direction. The two tangents divide each hull into two pieces. The edges belonging to one of thse pieces must be deleted (shown in yellow).
	Sorry, but you need Java to see the animation.	The final hull.

Because the merge can be done in linear time, the total time is O(n log n).

Three dimensions

You can use the left mouse button to look at any of the images below from a different direction.


	Sorry, but you need Java to see the animation.	Divide the points into two equal sized sets L and R such that all points of L are to the left of the most leftmost points in R. Recursively find the convex hull of L (shown in light blue) and R (shown in purple).
	Sorry, but you need Java to see the animation.	To merge in 3D need to construct a cylinder of triangles connecting the left hull and the right hull.
	Sorry, but you need Java to see the animation.	One edge of the cylinder AB is just the lower common tangent which can be computed just as in the two-dimensional case.
	Sorry, but you need Java to see the animation.	We next need to find a triangle ABC belonging to the cylinder which has AB as one of its edges. The third vertex of the triangle (C) must belong to either the left hull or the right hull. (In this case it belongs to the right hull.) Consequently, either AC is an edge of the left hull or BC is an edge of the right hull. (In this case BC is an edge of the right hull.) Hence, when considering possible candidates for the third vertex it is only necessary to consider candidates that are adjacent to A in the left hull or adjacent to B in the right hull. If we use a data structure for the hulls that allow us to find an adjacent vertex in constant time then the search for vertex C takes time proportional to the number of candidate vertices checked.
	Sorry, but you need Java to see the animation.	After finding triangle ABC we now have a new edge AC that joins the left hull and the right hull. We can find triangle ACD just as we did ABC. Continuing in this way, we can find all the triangles belonging to the cylinder, ending when we get back to AB. The total time to find the cylinder is O(n) so the algorithm takes O(n log n) time.

More dimensions

We can generalise this to any number of dimensions. However, the merge cannot be guaranteed to be completed in linear time, so the algorithm could take more time than O(n log n).

lambert@cse.unsw.edu.au

Last modified: Tue Sep 22 16:52:03 AET 1998