I finally figured out a nice way to implement dynamic convex hull that has a reasonable constant factor! I wouldn't be surprised if someone had done this before though.
Consider the problem of finding nested convex hulls in $$$O(n\log^2{n})$$$. The simplest way I know of is to make a convex hull data structure that supports point deletions, which is what I do here. It should in theory be possible to extend this implementation handle insertions as well.
This implementation is based on this paper by Overmars and van Leeuwen that describes a data structure for online fully dynamic convex hull in $$$O(\log^2{n})$$$ per operation. Directly implementing that is complicated and has a bad constant factor, so we'll do it a bit differently using ideas from [user:FizzyDavid]'s solution to 1270H.
The data structure
We need a data structure for points in the plane that can support * deleting a point in $$$O(\log^2{n})$$$ * returning the convex hull of k points in $$$O(k\log^2{n})$$$ time
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:
- Split the points in half by y-coordinate.
- Recursively build the hull for both halves
- Find a "bridge" that connects the two hulls. This can be done in $$$O(\log{n})$$$ with a binary search.
- Merge the two hulls with the bridge. Edges covered by the bridge are discarded.
To make this dynamic, we can turn this divide and conquer into a segment tree.
The paper explicitly stores the convex hull in a balanced binary search tree that supports split and concatenate in $$$O(\log^2{n})$$$. We'll instead implicitly represent the convex hull of each node in a segment tree.
Each node of the segment tree must store * Pointers to its left and right children * The bridge between the convex hulls of its children * The bottommost point of its leaves
Interestingly, computing the bridge can be done by querying its children in $$$O(\log{n})$$$.
Finding the bridge efficiently
A node of the segment tree must be able to compute the bridge of its children's convex hulls efficiently.
The paper has $$$10$$$ cases, but I think we only need $$$6$$$.
We have two segment tree nodes $$$p$$$ and $$$q$$$ that we want to find the bridge between. If they are both leaves, we are done.
Otherwise, let $$$a$$$ and $$$b$$$ be the points of the bridge of the first node and $$$c$$$ and $$$d$$$ be the points of the bridge of the second node. If the first (second) is a leaf, just set both $$$a$$$ and $$$b$$$ ($$$c$$$ and $$$d$$$) to the only point.
Repeat the following until we have one point on both hulls: * If $$$a\ne b$$$ and $$$a,b,c$$$ is in counterclockwise order, we can discard $$$b$$$ and all points above it. Set $$$p$$$ to $$$p$$$'s first child. * If $$$c\ne d$$$ and $$$b,c,d$$$ is in counterclockwise order, we can discard $$$c$$$ and all points below it. Set $$$q$$$ to $$$q$$$'s second child. * Otherwise, if $$$a=b$$$, we can discard $$$d$$$ and all points above it. Set $$$q$$$ to $$$q$$$'s first child. * Otherwise, if $$$c=d$$$, we can discard $$$a$$$ and all points below it. Set $$$p$$$ to $$$p$$$'s second child. * If we get here, $$$a$$$, $$$b$$$, $$$c$$$, $$$d$$$ are clockwise. Consider any horizontal line through the first point of $$$q$$$ separates 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 below it, or $$$d$$$ and all points above it. We either set $$$p$$$ to $$$p$$$'s second child or set $$$q$$$ to $$$q$$$'s first child.
After every iteration, we move either $$$p$$$ or $$$q$$$ to its children, so this process must terminate in $$$O(\log{n})$$$ iterations.
Implementation
Questions
Can all problems solvable by Overmars and van Leeuwen's technique be solved by this type of segment tree?