2018/12/24 by Bose, Prosenjit, Carmi, Paz, Dujmovic, Vida +1
#Computational Geometry (cs.CG) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.1812.09913
For any constants d≥ 1, ε>0, t>1, and any n-point set P⊂ℝd, we show that there is a geometric graph G=(P,E) having O(nlog2 nloglog n) edges with the following property: For any F⊆ P, there exists F+⊇ F, |F+| ≤ (1+ε)|F| such that, for any pair p,q∈ P∖ F+, the graph G-F contains a path from p to q whose (Euclidean) length is at most t times the Euclidean distance between p and q. In the terminology of robust spanners (Bose \et al, SICOMP, 42(4):1720--1736, 2013) the graph G is a (1+ε)k-robust t-spanner of P. This construction is sparser than the recent constructions of Buchin, Olàh, and Har-Peled (arXiv:1811.06898) who prove the existence of (1+ε)k-robust t-spanners with nlogO(d) n edges.