



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).



To merge in 3D need to construct a cylinder of triangles connecting
the left hull and the right hull.



One edge of the cylinder AB is just the lower common tangent which can
be computed just as in the twodimensional case.



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.



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.
