Abstract
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 sourcewise) 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.
BibTeX  Entry
@InProceedings{elkin_et_al:LIPIcs:2018:8749,
author = {Michael Elkin and Ofer Neiman},
title = {{Near Isometric Terminal Embeddings for Doubling Metrics}},
booktitle = {34th International Symposium on Computational Geometry (SoCG 2018)},
pages = {36:136:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770668},
ISSN = {18688969},
year = {2018},
volume = {99},
editor = {Bettina Speckmann and Csaba D. T{\'o}th},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/8749},
URN = {urn:nbn:de:0030drops87498},
doi = {10.4230/LIPIcs.SoCG.2018.36},
annote = {Keywords: metric embedding, spanners, doubling metrics}
}
Keywords: 

metric embedding, spanners, doubling metrics 
Collection: 

34th International Symposium on Computational Geometry (SoCG 2018) 
Issue Date: 

2018 
Date of publication: 

08.06.2018 