Merging two tangled convex hulls

Question

How to merge two tangled convex hulls (like this) to form a Convex Hull using Graham's Scan or anyother algorithm in linear time?

Answer 1

Basically, you use Andrew's modification of the Graham scan algorithm.

After the points are sorted in xy-order, the upper and lower hulls are computed in linear time. Since you already have the two convex hulls , the xy-sorting of the convex hull points will also take linear time (e.g., reverse the lower hulls and merge-sort four sorted lists).

Since the rest of the algorithm will take linear time, the overall runtime is linear as you requested.

Here is a reference to some short python code implementing Andrew's modification to Graham's scan. See also my answer here.