I finally figured out a nice way to implement dynamic convex hull that has a reasonable constant factor.

Disclaimer: Right now I only have deletions, but insertions should be possible too.

There is a paper by Overmars and van Leeuwen that describes a data structure for fully dynamic convex hull in $$$O(\log^2{n})$$$ per operation.

The left and right hulls are handled separately. From now on, we'll only consider the left hull.

We can build the hull using a divide and conquer strategy:

1. Split the points in half by y-coordinate.
2. Recursively build the hull for both halves
3. Find a "bridge" that connects the two hulls. This can be done in $$$O(\log{n})$$$ by a binary search.
4. Merge the two hulls with the bridge. Edges covered by the bridge are discarded.

The pattern of merges will form a binary tree.

To make this dynamic, the hulls are stored in binary search trees that support split and concatenate. In the last step, instead of discarding the edges, the edges are stored at the node so it can be restored later.

If we want to insert or delete point, we undo the merging of hulls on the path down to that point, adjust it, and merge back up.

Finding the bridge efficiently

We have two convex hulls and want to find the "bridge" to connect them.

The paper mentions $$$10$$$ cases, but I think we only need $$$6$$$.

Let's look at a pair of adjacent points on both hulls. Call them $$$a$$$, $$$b$$$, $$$c$$$ and $$$d$$$. If there is only one point on the first hull, set both $$$a$$$ and $$$b$$$ to that point.

• If $$$a\ne b$$$ and $$$a$$$,$$$b$$$,$$$c$$$ are in counterclockwise order, we can discard $$$b$$$ and all points to the right of it.
• If $$$c\ne d$$$ and $$$b$$$, $$$c$$$, $$$d$$$ are in counterclockwise order, we can discard $$$c$$$ and all points to the left of it.
• Otherwise, if $$$a=b$$$, we can discard $$$d$$$ and all points to the right of it.
• Otherwise, if $$$c=d$$$, we can discard $$$a$$$ and all points to the left of it.
• If we get here, $$$a$$$, $$$b$$$, $$$c$$$, $$$d$$$ are clockwise. Consider any horizontal line separating the two hulls. Depending on which side of the line the intersection of lines $$$ab$$$ and $$$cd$$$ are, we can either discard $$$a$$$ and all points to its left, or $$$d$$$ and all points to its right.