  The convex hull of a planar point set is the smallest convex polygon
containing each point in the set. The dynamic convex hull problem concerns
efficiently maintaining the convex hull of a set of points subject to additions
and removals. One algorithm for this problem uses two external balanced binary
search trees (BSTs) (M. H. Overmars, J. van Leeuwen 1981). We present the first
concurrent solution for this problem, which uses a single BST that stores
references to intermediate convex hull solutions at each node. We implement and
evaluate two lock-based approaches: a) fine-grained locking, where each node of
the tree is protected by a lock, and b) "finer-grained locking", where each
node contains a separate lock for each of the left and right chains. In our
throughput experiments, we observe that finer-grained locking yields an 8-60%
improvement over fine-grained locking, and a 38-61x improvement over
coarsegrained locking and software transactional memory (STM). When applied to
find the convex hull of static point sets, our approach outperforms a parallel
divide-and-conquer implementation by 2-4x using an equivalent number of
threads.
