Going through a text book on Data structures and algorithms(Steven Skiena), I came across convex hull problem.

So, objective is to find convex hull for a given set of points.

Books says:

Once you have the points sorted by x-coordinate, the points can be inserted from left to
right into the hull. Since the right-most point is always on the boundary, we know that 
it must appear in the hull. Adding this new right-most point may cause others to 
deleted, but we can quickly identify these points because they lie inside the polygon 
formed by adding the new point....
These points will be neighbors of the previous point we inserted, so they will be easy 
to find and delete. The total time is linear after the sorting has been done.

I am not able to understand how is this a linear time solution after sorting is done?

Every time we add a new point, we need to check for all exiting points whether they are inside polygon or not, which goes as 1,2,3,4,5...n operations. Adding these number of operations gives O(N*N).

Am I missing something here?

CodePudding user response：

Since you're constructing a polygon, you don't just have a set of points as your output, you also know which points are neighbours of which other points. There are two key things to note:

• Each point can only be deleted from the hull once,
• When you find a neighbour that you don't delete, you don't have to search further in that direction.

So each time you insert a point, you (possibly) remove some other points and you check at most two points that don't get removed. The total number of checks is therefore at most n for the points you delete, plus at most 2n for the neighbours you don't delete.

So you do O(n) convexity checks, and each check takes O(1) time since you only need to consider three points; hence, except for the initial sorting, the rest of the algorithm takes linear time.