(\mathcal{O}(k)\)-robust spanners in one dimension

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 \(\mathcal{O}(k)\)-robust if deleting \(k\) vertices only harms \(\mathcal{O}(k)\) o...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2018-03
Main Authors: Buchin, Kevin, Hulshof, Tim, Oláh, Dániel
Format: Article
Language:English
Subjects:
Apexes
Euclidean geometry
Euclidean space
Robustness
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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 \(\mathcal{O}(k)\)-robust if deleting \(k\) vertices only harms \(\mathcal{O}(k)\) other vertices. We show that on any one-dimensional set of \(n\) points, for any \(\varepsilon>0\), there exists an \(\mathcal{O}(k)\)-robust \(1\)-spanner with \(\mathcal{O}(n^{1+\varepsilon})\) edges. Previously it was only known that \(\mathcal{O}(k)\)-robust spanners with \(\mathcal{O}(n^2)\) edges exists and that there are point sets on which any \(\mathcal{O}(k)\)-robust spanner has \(\Omega(n\log{n})\) edges.
ISSN:2331-8422