Geodesic Spanners for Points in ${\mathbb{R}}^3$ amid Axis-parallel Boxes

Abstract

Let $P$ be a set of $n$ points in ${\mathbb{R}}^3$ amid a bounded number of obstacles. When obstacles are axis-parallel boxes, we prove that $P$ admits an $8\sqrt{3}$-spanner with $O(n{\log }^{3}n)$ edges with respect to the geodesic distance.