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

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

Add two edges to connect the new point to the remainder of the old hull. | ||

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

lambert@cse.unsw.edu.au Last modified: Tue Sep 22 16:53:01 AET 1998