  Recent years have witnessed a tremendous growth using topological summaries,
especially the persistence diagrams (encoding the so-called persistent
homology) for analyzing complex shapes. Intuitively, persistent homology maps a
potentially complex input object (be it a graph, an image, or a point set and
so on) to a unified type of feature summary, called the persistence diagrams.
One can then carry out downstream data analysis tasks using such persistence
diagram representations. A key problem is to compute the distance between two
persistence diagrams efficiently. In particular, a persistence diagram is
essentially a multiset of points in the plane, and one popular distance is the
so-called 1-Wasserstein distance between persistence diagrams. In this paper,
we present two algorithms to approximate the 1-Wasserstein distance for
persistence diagrams in near-linear time. These algorithms primarily follow the
same ideas as two existing algorithms to approximate optimal transport between
two finite point-sets in Euclidean spaces via randomly shifted quadtrees. We
show how these algorithms can be effectively adapted for the case of
persistence diagrams. Our algorithms are much more efficient than previous
exact and approximate algorithms, both in theory and in practice, and we
demonstrate its efficiency via extensive experiments. They are conceptually
simple and easy to implement, and the code is publicly available in github.
