How to maintain completely dynamic convex hull quickly?

Question

If there's no deletion, we can use $2$ balanced trees to maintain $2$ half convex hulls(up and down). In this way, we can insert $n$ points in $O(n\log n)$ time.(In the beginning, there are no points)

A completely dynamic convex hull means that I can insert and delete a point without rebuilding the whole convex hull, which costs $O(n)$'s time.

My problem is, is there any solutions to deleting points quickly? Maybe it could be solved with persistent data structures, but up to now, I haven't come up with any concrete method yet.

Answer 1

This was first solved by Jacob and Brodal in 2002; there is a recent arXiv submission of that work, "Dynamic Planar Convex Hull".

Answer 2

You can use my code. I implemented the ideas from the paper by Overmars and van Leeuwen. https://github.com/sumeetshirgure/DynamicPlanarHull/tree/master