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

Preprint · Kyungjin Cho, Jihun Shin, Eunjin Oh

- Archive id: arxiv:2312.16397
- Published: 2023-12-27
- arXiv: https://arxiv.org/abs/2312.16397
- Source URL: https://arxiv.org/abs/2312.16397
- PDF: https://arxiv.org/pdf/2312.16397
- Provenance: arxiv

## 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 $\\varepsilon$, our data structure has size $O\_{t,f}(n\\log n)$, and this allows us to compute an $(1+\\varepsilon)$-approximate distance in $G-F$ between $s$ and $s'$ can be computed in constant time for any two vertices $s$ and $s'$ 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+\\varepsilon)$-approximate shortest path in $G-F$ between $s$ and $s'$ in $O\_{t,f}(\\log^2 n\\log\\log n+\\textsf{sol})$ time for any two vertices $s$ and $s'$ and a set $F$ of failed vertices, where $\\textsf{sol}$ denotes the number of vertices in the returned path.

_Abstract reproduced under CC0-1.0 (arXiv descriptive metadata)._

---
Space Kitty Archive · https://space-kitty.com · API: https://space-kitty.com/api/v1 · MCP: https://space-kitty.com/mcp · Premium: $0.20/request via x402 (Base Sepolia (testnet)). Metadata: arXiv (CC0), OpenAlex (CC0), Europe PMC (CC BY/CC0 works), ClinicalTrials.gov.