# An Approximation Algorithm for Computing Shortest Paths in Weighted 3-d Domains

Preprint · Lyudmil Aleksandrov, Hristo Djidjev, Anil Maheshwari, Joerg-Rudiger Sack

- Archive id: arxiv:1102.3165
- Published: 2011-02-15
- arXiv: https://arxiv.org/abs/1102.3165
- Source URL: https://arxiv.org/abs/1102.3165
- PDF: https://arxiv.org/pdf/1102.3165
- Provenance: arxiv

## Abstract

We present the first polynomial time approximation algorithm for computing shortest paths in weighted three-dimensional domains. Given a polyhedral domain $\\D$, consisting of $n$ tetrahedra with positive weights, and a real number $\\eps\\in(0,1)$, our algorithm constructs paths in $\\D$ from a fixed source vertex to all vertices of $\\D$, whose costs are at most $1+\\eps$ times the costs of (weighted) shortest paths, in $O(\\C(\\D)\\frac{n}{\\eps^{2.5}}\\log\\frac{n}{\\eps}\\log^3\\frac{1}{\\eps})$ time, where $\\C(\\D)$ is a geometric parameter related to the aspect ratios of tetrahedra. The efficiency of the proposed algorithm is based on an in-depth study of the local behavior of geodesic paths and additive Voronoi diagrams in weighted three-dimensional domains, which are of independent interest. The paper extends the results of Aleksandrov, Maheshwari and Sack \[JACM 2005\] to three dimensions.

_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.