2020/11/01 by Evgeny Dantsin, Dantsin, Evgeny, Alexander Wolpert +1
Computer Science · Mathematics · #Computational Geometry and Mesh Generation #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #Geometric and Algebraic Topology #Topological and Geometric Data Analysis
paper · pdf · doi:10.48550/arxiv.2011.00616
openalex publication_date 2020/11/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
This paper is about similarity between objects that can be represented as points in metric measure spaces. A metric measure space is a metric space that is also equipped with a measure. For example, a network with distances between its nodes and weights assigned to its nodes is a metric measure space. Given points x and y in different metric measure spaces or in the same space, how similar are they? A well known approach is to consider x and y similar if their neighborhoods are similar. For metric measure spaces, similarity between neighborhoods is well captured by the Gromov-Hausdorff-Prokhorov distance, but it is NP-hard to compute this distance even in quite simple cases. We propose a tractable alternative: the radial distribution distance between the neighborhoods of x and y. The similarity measure based on the radial distribution distance is coarser than the similarity based on the Gromov-Hausdorff-Prokhorov distance but much easier to compute.