2026-07-20T05:25:17Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:8749 2024-03-06T10:42:34Z ddc:004 open_access

Near Isometric Terminal Embeddings for Doubling Metrics Elkin, Michael Neiman, Ofer metric embedding spanners doubling metrics Given a metric space (X,d), a set of terminals K subseteq X, and a parameter t >= 1, we consider metric structures (e.g., spanners, distance oracles, embedding into normed spaces) that preserve distances for all pairs in K x X up to a factor of t, and have small size (e.g. number of edges for spanners, dimension for embeddings). While such terminal (aka source-wise) metric structures are known to exist in several settings, no terminal spanner or embedding with distortion close to 1, i.e., t=1+epsilon for some small 0<epsilon<1, is currently known. Here we devise such terminal metric structures for doubling metrics, and show that essentially any metric structure with distortion 1+epsilon and size s(|X|) has its terminal counterpart, with distortion 1+O(epsilon) and size s(|K|)+1. In particular, for any doubling metric on n points, a set of k=o(n) terminals, and constant 0<epsilon<1, there exists - A spanner with stretch 1+epsilon for pairs in K x X, with n+o(n) edges. - A labeling scheme with stretch 1+epsilon for pairs in K x X, with label size ~~ log k. - An embedding into l_infty^d with distortion 1+epsilon for pairs in K x X, where d=O(log k). Moreover, surprisingly, the last two results apply if only K is a doubling metric, while X can be arbitrary. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Michael Elkin and Ofer Neiman 2018 Is Part Of LIPIcs, Volume 99, 34th International Symposium on Computational Geometry (SoCG 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SoCG.2018.36 urn:nbn:de:0030-drops-87498 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2018.36 eng https://creativecommons.org/licenses/by/3.0/legalcode