2026-08-12T08:04:50Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:19958 2024-06-06T06:21:13Z ddc:004 open_access

Topological k-Metrics Barkan, Willow Bennett, Huck Nayyeri, Amir k-metrics metric embeddings computational topology simplicial complexes Metric spaces (X, d) are ubiquitous objects in mathematics and computer science that allow for capturing pairwise distance relationships d(x, y) between points x, y ∈ X. Because of this, it is natural to ask what useful generalizations there are of metric spaces for capturing "k-wise distance relationships" d(x_1, …, x_k) among points x_1, …, x_k ∈ X for k > 2. To that end, Gähler (Math. Nachr., 1963) (and perhaps others even earlier) defined k-metric spaces, which generalize metric spaces, and most notably generalize the triangle inequality d(x₁, x₂) ≤ d(x₁, y) + d(y, x₂) to the "simplex inequality" d(x_1, …, x_k) ≤ ∑_{i=1}^k d(x_1, …, x_{i-1}, y, x_{i+1}, …, x_k). (The definition holds for any fixed k ≥ 2, and a 2-metric space is just a (standard) metric space.) In this work, we introduce strong k-metric spaces, k-metric spaces that satisfy a topological condition stronger than the simplex inequality, which makes them "behave nicely." We also introduce coboundary k-metrics, which generalize 𝓁_p metrics (and in fact all finite metric spaces induced by norms) and minimum bounding chain k-metrics, which generalize shortest path metrics (and capture all strong k-metrics). Using these definitions, we prove analogs of a number of fundamental results about embedding finite metric spaces including Fréchet embedding (isometric embedding into 𝓁_∞) and isometric embedding of all tree metrics into 𝓁₁. We also study relationships between families of (strong) k-metrics, and show that natural quantities, like simplex volume, are strong k-metrics. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Willow Barkan and Huck Bennett and Amir Nayyeri 2024 Is Part Of LIPIcs, Volume 293, 40th International Symposium on Computational Geometry (SoCG 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SoCG.2024.13 urn:nbn:de:0030-drops-199585 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2024.13 eng https://creativecommons.org/licenses/by/4.0/legalcode