{O}(k)-robust spanners in one dimension
Kevin Buchin, Tim Hulshof, Dániel Oláh · TU/e Research Portal · 2018
A geometric t-spanner on a set of points in Euclidean space is a graph containing for every pair of points a path of length at most t times the Euclidean distance between the points. Informally, a spanner is O(k)-robust if deleting k vertices only harms O(k) other vertices. We show that on any one-dimensional set of n points, for any ε>0, there exists an O(k)-robust 1-spanner with O(n1+ε) edges. Previously it was only known that O(k)-robust spanners with O(n2) edges exists and that there are point sets on which any O(k)-robust spanner has Ω(nlogn) edges.