  In this paper, we design parallel write-efficient geometric algorithms that
perform asymptotically fewer writes than standard algorithms for the same
problem. This is motivated by emerging non-volatile memory technologies with
read performance being close to that of random access memory but writes being
significantly more expensive in terms of energy and latency. We design
algorithms for planar Delaunay triangulation, $k$-d trees, and static and
dynamic augmented trees. Our algorithms are designed in the recently introduced
Asymmetric Nested-Parallel Model, which captures the parallel setting in which
there is a small symmetric memory where reads and writes are unit cost as well
as a large asymmetric memory where writes are $\omega$ times more expensive
than reads. In designing these algorithms, we introduce several techniques for
obtaining write-efficiency, including DAG tracing, prefix doubling,
reconstruction-based rebalancing and $\alpha$-labeling, which we believe will
be useful for designing other parallel write-efficient algorithms.
