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₁, p₂, . . , p_n}. We begin by construction triangle. We now deal with the problem of adding a point  p_i to an existing convex hull CH_i-1.

At this stage there are two possibilities

1. p_i is inside CH_i-1 i.e., p_i belongs to  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_i is always on the right side of an edge. If it is, then CH_i = CH_i-1.
2. p_i is outside CH_i-1 i.e., p_i not belongs to CH_i-1. This can be done by finding the two tangent lines from p_i to 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 CH_i = CH_i-1U p_i.

How to find such p_i?

Scan CH_i-1in clockwise order

• If  p_t  is such that p_i is on the right of edge (p_i-1 p_t) and the left of edge (p_t p_i+1).
• If  p_t is such that p_i is on the left of edge (p_i-1 p_t) and right of edge (p_t p_t+1).
• If both are true, then p_i can be added in existing convex hull.
   

Clearly, the scan of CH_i-1 is sufficient to find both points.

Analysis

Since, each step involves a scan of CH_i-1. Therefore, the complexity is 3 + 4 + . . . + (n -1) = O(n²).

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 the n belongs to S points by their x-coordinate
CH  ←  triangle (p₁, p₂, p₃)

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

        // find the upper tangency point
        u = j
        while (p_ih₄ is not tangent to CH) do
                if (u ≠  j) then
                        remove h₄  from CH
                u = u -1

        // find the lower tangency point
        I = j
        while (p_ih_l is not tangent to CH) do
                if ( I ≠ u) then
                        remove h_i from CH
                I = I + 1

        INSERT p_i in CH between h_u and h_i

Analysis

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