  This paper presents ParGeo, a multicore library for computational geometry.
ParGeo contains modules for fundamental tasks including $k$d-tree based spatial
search, spatial graph generation, and algorithms in computational geometry.
  We focus on three new algorithmic contributions provided in the library.
First, we present a new parallel convex hull algorithm based on a reservation
technique to enable parallel modifications to the hull. We also provide the
first parallel implementations of the randomized incremental convex hull
algorithm as well as a divide-and-conquer convex hull algorithm in
$\mathbb{R}^3$. Second, for the smallest enclosing ball problem, we propose a
new sampling-based algorithm to quickly reduce the size of the data set. We
also provide the first parallel implementation of Welzl's classic algorithm for
smallest enclosing ball. Third, we present the BDL-tree, a parallel
batch-dynamic $k$d-tree that allows for efficient parallel updates and $k$-NN
queries over dynamically changing point sets. BDL-trees consist of a
log-structured set of $k$d-trees which can be used to efficiently insert,
delete, and query batches of points in parallel.
  On 36 cores with two-way hyper-threading, our fastest convex hull algorithm
achieves up to 44.7x self-relative parallel speedup and up to 559x speedup
against the best existing sequential implementation. Our smallest enclosing
ball algorithm using our sampling-based algorithm achieves up to 27.1x
self-relative parallel speedup and up to 178x speedup against the best existing
sequential implementation. Our implementation of the BDL-tree achieves
self-relative parallel speedup of up to 46.1x. Across all of the algorithms in
ParGeo, we achieve self-relative parallel speedup of 8.1--46.61x.
