## 2 Bypassing Matchings  
We propose to bypass the overwhelming matching problem in the computation of 0-dimensional bottleneck distance by showing that the value produced by the bottleneck distance formula can be recovered by considering only a few cases. We will show that these cases naturally come up in the process of minimizing the output of the norm. We first note that for most practical applications to data analysis of 0-dimensional persistence diagrams, where all components are assumed to be born at the beginning of the filtration for persistent homology, all non-trivial points lie in the vertical axis (or equivalently for persistence barcodes, all bars begin at time \(t=0\)). Hence, in this case, if \(\delta_{x}\), and \(\delta_{\phi(x)}\) are the death times respectively for \(x\) and its matched point \(\phi(x)\), we have that  
\[||x-\phi(x)||_{\infty}= \begin{cases}\max(\delta_{x},\delta_{\phi(x)})/2&\text {if }\phi(x)\in\Delta\\ |\delta_{x}-\delta_{\phi(x)}|&\text{otherwise.}\end{cases}  \tag{1}\]  
This suggests that while it is natural to do a point-to-point matching between diagrams, there are cases when we are better off matching a point to the diagonal. For a point \(x\in X\) and \(\phi(x)\in Y\), this happens precisely when  
\[\max(\delta_{x},\delta_{\phi(x)})>2\min(\delta_{\phi(x)},\delta_{x}). \tag{2}\]  
Figure 2a illustrates this point. Therefore, unless (2) is satisfied, it is our priority to match a non-trivial point in a diagram \(X\) with a non-trivial point in another diagram. This supports the interpretation that the bottleneck distance is the cost of transforming one diagram to another. We are now ready to present our algorithm for computing 0-dimensional bottleneck distance between two persistence diagrams. We first induce and ordering of the death times in both diagrams and define a bijection that we can methodically modify to optimize the norm between matched points and recover the desired matching that achieves the bottleneck distance. The proof of Lemma 1 provides the basic argument that allows us to bypass the overwhelming matching problem. Lemma 2 proceeds in the same manner and identifies all other possible instances where the bottleneck matching is achieved, and the exact bottleneck distance in each case. Let \(X\) and \(Y\) be two 0-dimensional persistence diagrams whose death time entries are arranged from largest to smallest. Equivalently, \(X\) and \(Y\) can be thought of as persistence barcodes whose bars are arranged from longest to shortest. Without loss of generality, assume that \(X\) has at most as many points as \(Y\) has. We remark that this pre-processing is equivalent to considering the bijection \(\phi\) that matches points between \(X\) and \(Y\) according to the relative ranking of death times from largest to smallest, and where unmatched points in \(Y\) are matched to the diagonal. Let \(N=length(X)\) and define  
\[Z=[z_{i}]_{1}^{length(Y)}\text{ where }z_{i}= \begin{cases}|x_{i}-y_{i}|&\text {if }i\leq N\\ y_{i}/2&\text{otherwise}\end{cases} \]  
Figure 2: Examples of point-matching between persistence diagrams highlighting the resulting bottleneck distance. Points in each diagrams are shape coded and matched points are color coded. (**a**) illustrates when diagonal matching achieves the bottleneck distance. (**b**) is used in the proof of Lemma 1 and (**c**,**d**) in Lemma 2.  
and \(l=\arg\max(Z)\). Lemma 1: _Let \(X\), \(Y\), \(Z\), \(N\) and \(\phi\) be defined as above. If \(N<length(Y)\) and \(\max(Z)\leq y_{N+1}/2\), then_  
\[d_{B}(X,Y)=y_{N+1}/2\]  
_where \(y_{N+1}\) is the largest death time of a point in \(Y\) matched to the diagonal._  
Proof. : For the bijection \(\phi\) corresponding to the pre-processing described above, it follows that  
\[\max_{x\in X}||x-\phi(x)||_{\infty}=y_{N+1}/2.\]  
Figure 2b illustrates this case where the point matched to the diagonal maximizes the norm.