Approximate Distance and Shortest-Path Oracles for Fault-Tolerant Geometric Spanners

Abstract

In this paper, we present approximate distance and shortest-path oracles for fault-tolerant Euclidean spanners motivated by the routing problem in real-world road networks. An $f$-fault-tolerant Euclidean $t$-spanner for a set $V$ of $n$ points in ${\mathbb{R}}^d$ is a graph $G=(V,E)$ where, for any two points $p$ and $q$ in $V$ and a set $F$ of $f$ vertices of $V$, the distance between $p$ and $q$ in $G-F$ is at most $t$ times their Euclidean distance. Given an $f$-fault-tolerant Euclidean $t$-spanner $G$ with $O(n)$ edges and a constant $\epsilon$, our data structure has size $O_{t,f}(n\log n)$, and this allows us to compute an $(1+\epsilon )$-approximate distance in $G-F$ between $s$ and $s^{\prime }$ can be computed in constant time for any two vertices $s$ and $s^{\prime }$ and a set $F$ of $f$ failed vertices. Also, with a data structure of size $O_{t,f}(n\log n\log \log n)$, we can compute an $(1+\epsilon )$-approximate shortest path in $G-F$ between $s$ and $s^{\prime }$ in $O_{t,f}({\log }^{2}n\log \log n+\text{sol})$ time for any two vertices $s$ and $s^{\prime }$ and a set $F$ of failed vertices, where $\text{sol}$ denotes the number of vertices in the returned path.

AAAI 2024