  This paper presents an algorithm for the efficient approximation of the
saddle-extremum persistence diagram of a scalar field. Vidal et al. introduced
recently a fast algorithm for such an approximation (by interrupting a
progressive computation framework). However, no theoretical guarantee was
provided regarding its approximation quality. In this work, we revisit the
progressive framework of Vidal et al. and we introduce in contrast a novel
approximation algorithm, with a user controlled approximation error,
specifically, on the Bottleneck distance to the exact solution. Our approach is
based on a hierarchical representation of the input data, and relies on local
simplifications of the scalar field to accelerate the computation, while
maintaining a controlled bound on the output error. The locality of our
approach enables further speedups thanks to shared memory parallelism.
Experiments conducted on real life datasets show that for a mild error
tolerance (5% relative Bottleneck distance), our approach improves runtime
performance by 18% on average (and up to 48% on large, noisy datasets) in
comparison to standard, exact, publicly available implementations. In addition
to the strong guarantees on its approximation error, we show that our algorithm
also provides in practice outputs which are on average 5 times more accurate
(in terms of the L2-Wasserstein distance) than a naive approximation baseline.
We illustrate the utility of our approach for interactive data exploration and
we document visualization strategies for conveying the uncertainty related to
our approximations.
