The basic idea of incremental convex hull algorithm is as follows. First take a subset of the input small enough so that the problem is easily solved. Then, one by one add remaining elements (of input) while maintaining the solution at each step.

We illustrate this algorithm by building a convex hull of given *S *= {*p*_{1},
*p*_{2}, . . , *p _{n}*}. We begin by construction triangle. We now deal
with the problem of adding a point

At this stage there are two possibilities

*p*is inside_{i}*CH*_{i-1}i.e.,*p*belongs to_{i}*CH*_{i-1}. This is easy to detect in linear time by scanning the points of*CH*_{i-1}in clockwise order and checking whether or not*p*is always on the right side of an edge. If it is, then_{i}*CH*_{i }=*CH*_{i-1}.*p*is outside_{i}*CH*_{i-1}i.e.,*p*not belongs to_{i}*CH*_{i-1}. This can be done by finding the two tangent lines from*p*to_{i}*CH*_{i-1}.

Since there is no subset of three collinear points (non
degeneracy hypothesis), a tangent line meets *CH*_{i-1} at a single vertex *p _{i}*.
If this is the case, then

How to find such *p _{i}*?

ScanCH_{i-1}in clockwise order

- If
pis such that_{t}pis on the right of edge (_{i}p_{i-1 }p) and the left of edge (_{t}p_{t }p_{i+1}).- If
pis such that_{t}pis on the left of edge (_{i}p_{i-1 }p) and right of edge (_{t}p_{t}p_{t+}_{1}).- If both are true, then
pcan be added in existing convex hull._{i}

Clearly, the scan of *CH*_{i-1} is sufficient to find both
points.

Since, each step involves a scan of *CH*_{i-1}. Therefore, the
complexity is 3 + 4 + . . . + (*n *-1) = O(*n*^{2}).

We can clearly, improve this algorithm by presorting the
given set *S*. The pseudo-code of the improved algorithm is as follows.

INCREMENTAL CONVEX HULL (S)Sort thenbelongs toSpoints by theirx-coordinateCH← triangle (p_{1},p_{2},p_{3})

for(4 ≤i≤n)do← Index of the rightmost point of

jCH

// find the upper tangency point

u=j

while(p_{i}h_{4 }is not tangent toCH)do

if(u≠j)then

removeh_{4 }fromCH=

uu-1// find the lower tangency point

I=j

while(p_{i}h_{l}is not tangent toCH)do

if(I≠u)then

removehfrom_{i}CH=

II+ 1INSERT

pin_{i}CHbetweenhand_{u}h_{i}

Each step of this algorithm consists of eliminating some
points. Since, we cannot eliminate more than n points, this gives the bound on
the running time. Hence, the inserting of n points takes O(*n*) time. In addition,
due to the dominating cost of sorting, the complexity of the algorithm is
O(*n log n*).