  This paper presents a unified computational framework for the estimation of
distances, geodesics and barycenters of merge trees. We extend recent work on
the edit distance [106] and introduce a new metric, called the Wasserstein
distance between merge trees, which is purposely designed to enable efficient
computations of geodesics and barycenters. Specifically, our new distance is
strictly equivalent to the L2-Wasserstein distance between extremum persistence
diagrams, but it is restricted to a smaller solution space, namely, the space
of rooted partial isomorphisms between branch decomposition trees. This enables
a simple extension of existing optimization frameworks [112] for geodesics and
barycenters from persistence diagrams to merge trees. We introduce a task-based
algorithm which can be generically applied to distance, geodesic, barycenter or
cluster computation. The task-based nature of our approach enables further
accelerations with shared-memory parallelism. Extensive experiments on public
ensembles and SciVis contest benchmarks demonstrate the efficiency of our
approach -- with barycenter computations in the orders of minutes for the
largest examples -- as well as its qualitative ability to generate
representative barycenter merge trees, visually summarizing the features of
interest found in the ensemble. We show the utility of our contributions with
dedicated visualization applications: feature tracking, temporal reduction and
ensemble clustering. We provide a lightweight C++ implementation that can be
used to reproduce our results.
