Sublinear but simple Dynamic Convex Hull algorithm?

Question

I need to solve dynamic convex hull algorithm problem, i.e. maintaining the convex hull of 2D points, where I can add and delete points.

The naive approach is clearly O(N); whenever one of the N points is added/deleted, we recompute the convex hull from scratch. However, I cannot afford linear time, so I am looking for a sublinear algorithm. So far, I have found a bunch of paper all of which describe some sophisticated algorithm with crazy time bounds which would take ages to implement. Even the oldest efficient algorithm, due to Overmars and Leeuween, which is O(log^2 N) seems way too complicated. (As usual, most of algorithms described in such papers have tons of dependencies in terms of structures/algorithms from other, referenced papers)

I am looking for something simpler, not necessarily novel, which performs better than linear in the worst case (e.g. O(sqrt N)). Finally, I don't mind if the time is amortized. Any ideas?

(By simple, I primarily mean something that does not require more than a few hundred lines of code.)

Answer 1

I think what you seek does not exist. The Overmars and vanLeeuwen algorithm is not that complicated, and it seems in some sense necessary. First, change the problem to maintaining the upper hull and the lower hull separately. Second, construct each by divide-and-conquer, but retain the intermediate tree structures, so that you know the hulls of the 1/2-sets, the 1/4-sets, etc. Now, when you delete a point, you recompute only its ancestors in the tree. When you add a point, you find out to which leaf it joins, and again recomputed upwards to the root.

I think if you ignore the details in their paper, and just follow this high-level sketch, and implement all the steps in the most mindless manner, it will not be complicated, and will be sublinear.

---

M. H. Overmars and J. van Leeuwen. Maintenance of configurations in the plane. J. Comput. Syst. Sci., 23:166-204, 1981.