Skip to main content

Convex Hulls

Recommended Week

Year 1 : All Weeks

Originator

Simon Hollis

Aim

To propose and develop your own algorithm, spot weaknesses and suggest improvements, analyse running time and try to improve performance.

Task

The problem of finding the convex hull of a set of points is a classic one in Computer Science. Since it simple, geometric and has many possible solutions, it is a nice one to use as a case example to get students to try and generate their own algorithms to solve it.

Describe the problem with the aid of a drawing on the whiteboard and show the intended end result. Then ask students to propose their own algorithms to solve the problem.

If you need some starters, you could suggest comparing (x,y) coordinates or inter-point distances or looking at the centre of mass of the points etc.

If you are lucky, there will be several different algorithms proposed by the students. Once you have this set, ask them to suggest what their running times might be, and what they think the optimal solution time would be.

Getting the individual students to explain their algorithms on the whiteboard is also a valuable development opportunity in communication.

Then, you can ask the students to choose their favourite solution and concentrate on optimising it.

If any solutions are O(n^2) or greater, see if they can propose some optimisations to reduce the running time.

Book

Cormen, Leiserson, Rivest and Stein's "Introduction to Algorithms" has a comprehensive review of serveral algorithms, with an illustration of one with O(nh) running time [h = number of vertices in the final solution].