Gromov-Hausdorff distances on $p$-metric spaces and ultrametric spaces

We investigate certain subsets $\mathcal{M}_p$ of the collection of all compact metric spaces $\mathcal{M}$ which are characterized by satisfying a strengthened form of the triangle inequality which encompasses, for example, the strong triangle inequality satisfied by ultrametric spaces. We identify a family of Gromov-Hausdorff like distances on $\mathcal{M}_p$ and study geometric and computational properties of these distances as well as the stability of certain canonical projections $\mathfrak{S}_p:\mathcal{M}\rightarrow \mathcal{M}_p$. For the collection $\mathcal{U}$ of all ultrametric spaces, as a special example of $\mathcal{M}_p$, we explore an interleaving-type distance and reveal its relationship with the Gromov-Hausdorff distance. We study the geodesic property of $\mathcal{M}_p$ equipped with different distances. We exploit special properties of ultrametric spaces and devise efficient algorithms for computing the family of Gromov-Hausdorff distances which we prove run in polynomial time when restricted to special classes of ultrametric spaces. We generalize some of our results to the case of ultra-dissimilarity spaces.