dragonslayerintraining's blog

By dragonslayerintraining, history, 20 months ago, In English

I finally figured out a nice way to implement dynamic convex hull with a reasonable constant factor! I expect this will be "well known in China" 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 be possible to extend this implementation to 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 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 left 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

In a leaf node, we just pretend the bridge is between the point and itself.

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. 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.

Repeat the following until both $$$p$$$ and $$$q$$$ are leaves.

  • If $$$a\ne b$$$ ($$$p$$$ is not a leaf) and $$$a,b,c$$$ is in counterclockwise order, we can discard $$$b$$$ and all points above it. Set $$$p$$$ to its 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 its second child.

  • Otherwise, if $$$a=b$$$, we can discard $$$d$$$ and all points above it. Set $$$q$$$ to its first child.

  • Otherwise, if $$$c=d$$$, we can discard $$$a$$$ and all points below it. Set $$$p$$$ to its second child.

  • If we get here, $$$a$$$, $$$b$$$, $$$c$$$, $$$d$$$ are clockwise. The horizontal line through the bottommost 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 its second child or set $$$q$$$ to its first child.

After every iteration, we move either $$$p$$$ or $$$q$$$ to its children, so this process must terminate in $$$O(\log{n})$$$ iterations.

Extracting the convex hull

To compute the convex hull, we define a recursive function that does the following:

  • Given a node and two points $$$l$$$ and $$$r$$$ on the convex hull of the node, output the points on the convex hull between them, inclusive.

We just need to handle a few cases.

  • If the bridge is contained between $$$l$$$ and $$$r$$$, we recurse on both children
  • If the bridge is fully covered, we recurse on the child that isn't fully covered.

It is impossible for the bridge to be partially covered.

Deletions

Deletions are kind of annoying because there is nothing that naturally acts as identity. I just removed all nodes with one child from the tree to avoid adding extra cases to the bridge-finding.

Implementation

Code

Questions

Another problem mentioned in the paper is maintaining points in the plane such that no point has larger $$$x$$$ and $$$y$$$ coordinates.

1270H mentioned above is similar.

What are other problems solvable this way?

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

Is it possible to optimize all these to $$$O(n\log{n})$$$? Apparently it is possible for dynamic convex hull at least.

 
 
 
 
  • Vote: I like it
  • +229
  • Vote: I do not like it

»
20 months ago, # |
  Vote: I like it +24 Vote: I do not like it

Auto comment: topic has been updated by dragonslayerintraining (previous revision, new revision, compare).

»
19 months ago, # |
  Vote: I like it +33 Vote: I do not like it

Since you're only considering deletions, this paper gives an easier data structure with amortized $$$\mathcal{O}(\log n)$$$ deletion time. Here's a quick unoptimized implementation I did based on the paper, seems to be around twice as fast as yours.

The basic idea is to store the hulls in linked lists (to avoid a log factor) and only store the part of the hull that's not on the parent's hull. (In particular, the whole convex hull can be found at the root.) This way, points only move up the tree and it turns out that changes in the bridges can be amortized by points moving up. With these bridges, one could also do things such as extreme point queries.

Is there an online judge for the nested convex hull problem?