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 = {p1, p2, . . , pn}. We begin by construction triangle. We now deal with the problem of adding a point pi to an existing convex hull CHi-1.
At this stage there are two possibilities
Since there is no subset of three collinear points (non degeneracy hypothesis), a tangent line meets CHi-1 at a single vertex pi. If this is the case, then CHi = CHi-1U pi.
How to find such pi?
Scan CHi-1in clockwise order
- If pt is such that pi is on the right of edge (pi-1 pt) and the left of edge (pt pi+1).
- If pt is such that pi is on the left of edge (pi-1 pt) and right of edge (pt pt+1).
- If both are true, then pi can be added in existing convex hull.
Clearly, the scan of CHi-1 is sufficient to find both points.
Since, each step involves a scan of CHi-1. Therefore, the complexity is 3 + 4 + . . . + (n -1) = O(n2).
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 (p1, p2, p3)for (4 ≤ i ≤ n ) do
j ← Index of the rightmost point of CH// find the upper tangency point
u = j
while (pih4 is not tangent to CH) do
if (u ≠ j) then
remove h4 from CH
u = u -1// find the lower tangency point
I = j
while (pihl is not tangent to CH) do
if ( I ≠ u) then
remove hi from CH
I = I + 1INSERT pi in CH between hu and hi
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).