Finding the minimal convex hull containing a set of 2D points is a standard problem. The standard approach is a somewhat clunky one:

The following "divide and conquer" algorithm - though * worst case* O(N

It is possible to implement this algorithm by means of a single call to a general recursive primitive but as a special case serves for all but the uppermost level of the recursion we implement the simpler case recursively and code the first level explicitly.

Note that in the following a *set* refers to an unordered collection of objects
while a *list* is an * ordered* collection of obects.

The basic primitive *LeftHull* accepts two points **a** and **b** and a **set**** S** of points
known to lie to the "left" of the line

We can define

*LeftHull*(**a**,**b**,*S*_{ab})

if ** S**=

Set n_{ab} | = | æ | a_{y}-b_{y} | ö |

è | b_{x}-a_{x} | ø |

Find

Set n_{cb} | = | æ | c_{y}-b_{y} | ö |

è | b_{x}-c_{x} | ø |

Create a new point set

For each

Set n_{ac} | = | æ | a_{y}-c_{y} | ö |

è | c_{x}-a_{x} | ø |

Create a new point set

For each

Discard all points remaining in

Return list obtained by concatenating

End

The top level of the recursion is given simply a set of points ** S** and proceeds as follows:

Find two distinct points

Set n_{ab} | = | æ | a_{y}-b_{y} | ö |

è | b_{x}-a_{x} | ø |

Create empty sets

For each

if (

if (

Discard all points remaining in

The unlooped edge list of the minimal convex hull of

Note that if **a** and **b** are chosen by minimal and maximal *y* then the two "halves"
of solution correspond to the left and right hand boundaries of the hull.

This method generalises for three or higher dimensional convex hulls in the obvious manner.
In 3D, the recursive primitive accepts three points and a set of points known to lie to one side
of the plane defined by them and to project into that plane to points within the triangle.
It finds that point furthest from the plane and calls itself
for three distinct subsets of the inherited set while discarding all those points within the constructed tetrahedron.

Glossary Contents Author

Copyright (c) Ian C G Bell 1998

Web Source: www.iancgbell.clara.net/maths or www.bigfoot.com/~iancgbell/maths

18 Nov 2006.