Near isometric terminal embeddings for doubling metrics

DOI10.4230/LIPICS.SOCG.2018.36zbMATH Open1489.68212arXiv1802.07967OpenAlexW2962921238MaRDI QIDQ5115804FDOQ5115804

Authors: Michael Elkin, Ofer Neiman 

Publication date: 18 August 2020

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.

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

Recommendations

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

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)

Cites Work

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

Cited In (5)

• Lossless prioritized embeddings
• Near isometric terminal embeddings for doubling metrics
• Making doubling metrics geodesic
• Terminal 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)