Near isometric terminal embeddings for doubling metrics

DOI10.4230/LIPICS.SOCG.2018.36MaRDI QIDQ5115804zbMATH OpenOpenAlexFDO

Authors Michael Elkin, Ofer Neiman

Publication date 18 August 2020

Full work available at URL https://arxiv.org/abs/1802.07967

zbMATH Keywords

metric embeddingspannersdoubling metrics

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Metric embeddings as related to computational problems and algorithms (68R12)

Abstract: Given a metric space $(X,d)$, a set of terminals $KsubseteqX$, and a parameter $tge1$, we consider metric structures (e.g., spanners, distance oracles, embedding into normed spaces) that preserve distances for all pairs in $KimesX$ 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 {em 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: (1) A spanner with stretch $1+epsilon$ for pairs in $KimesX$, with $n+o(n)$ edges. (2) A labeling scheme with stretch $1+epsilon$ for pairs in $KimesX$, with label size $approxlogk$. (3) An embedding into $el{l}_{i}nft{y}^d$ with distortion $1+epsilon$ for pairs in $KimesX$, where $d=O(logk)$. Moreover, surprisingly, the last two results apply if only $K$ is a doubling metric, while $X$ can be arbitrary.

Recommendations

• Near isometric terminal embeddings for doubling metrics
• Terminal embeddings
• Terminal embeddings
• On hierarchical routing in doubling metrics
• On hierarchical routing in doubling metrics

Cites work

• scientific article; zbMATH DE number 1749054 (Why is no real title available?)
• An Optimal Dynamic Spanner for Doubling Metric Spaces
• Bypassing Erdős' girth conjecture: hybrid stretch and sourcewise spanners
• Bypassing the embedding
• Deformable spanners and applications
• Distance estimation and object location via rings of neighbors
• Extensions of Lipschitz mappings into a Hilbert space
• Fast Construction of Nets in Low-Dimensional Metrics and Their Applications
• Geometric Spanner Networks
• Graph minors. X: Obstructions to tree-decomposition
• Low dimensional embeddings of doubling metrics
• NEW SPARSENESS RESULTS ON GRAPH SPANNERS
• New Doubling Spanners: Better and Simpler
• New pairwise spanners
• On Lipschitz embedding of finite metric spaces in Hilbert space
• On Pairwise Spanners
• On hierarchical routing in doubling metrics
• On sparse spanners of weighted graphs
• On the distortion required for embedding finite metric spaces into normed spaces
• Optimal Euclidean Spanners
• Plongements lipschitziens dans ${\bbfR}\sp n$
• Ramsey partitions and proximity data structures
• Reachability preservers: new extremal bounds and approximation algorithms
• Small hop-diameter sparse spanners for doubling metrics
• Sparse source-wise and pair-wise distance preservers
• Terminal embeddings
• The geometry of graphs and some of its algorithmic applications

Cited in

(5)

• Near isometric terminal embeddings for doubling metrics
• Making doubling metrics geodesic
• Terminal embeddings
• Lossless prioritized embeddings
• Labelings vs. embeddings: on distributed and prioritized representations of distances

This page was built for publication: Near isometric terminal embeddings for doubling metrics

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5115804)