Incremental Convex Hull

 

 

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

  1. pi is inside CHi-1 i.e., pi belongs to  CHi-1. This is easy to detect in linear time by scanning the points of CHi-1 in clockwise order and checking whether or not pi is always on the right side of an edge. If it is, then CHi = CHi-1.
  2. pi is outside CHi-1 i.e., pi not belongs to CHi-1. This can be done by finding the two tangent lines from pi to CHi-1.

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

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

 

Analysis

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 + 1

        INSERT pi in CH between hu and hi

 

 

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