Dynamic convex hull implementation

Revision en2, by dragonslayerintraining, 2020-04-13 07:00:10

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:

  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})$$$ with a binary search.
  4. 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

Code

Questions

Can all problems solvable by Overmars and van Leeuwen's technique be solved by this type of segment tree?

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en6 English dragonslayerintraining 2020-04-13 07:57:26 28 Tiny change: 'mentation handle in' -> 'mentation to handle in' (published)
en5 English dragonslayerintraining 2020-04-13 07:46:15 9
en4 English dragonslayerintraining 2020-04-13 07:42:35 747 Tiny change: 'It should in theory be possib' -> 'It should be possib'
en3 English dragonslayerintraining 2020-04-13 07:21:06 968
en2 English dragonslayerintraining 2020-04-13 07:00:10 9506
en1 English dragonslayerintraining 2020-04-13 03:51:11 2307 Initial revision (saved to drafts)