Let $S$ be a set of $n$ points on a polyhedral terrain $\mathcal{T}$ in $\mathbb{R}^3$, and let $\varepsilon>0$ be a fixed constant. We prove that $S$ admits a $(2+\varepsilon)$-spanner with $O(n\log n)$ edges with respect to the geodesic distance. This is the first spanner with constant spanning ratio and a near-linear number of edges for points on a terrain. On our way to this result, we prove that any set of $n$ weighted points in $\mathbb{R}^d$ admits an additively weighted $(2+\varepsilon)$-spanner with $O(n)$ edges; this improves the previously best known bound on the spanning ratio (which was $5+\varepsilon$) and almost matches the lower bound.

Let S be a set S of n points on a polyhedral terrain T in ℝ3, and let ∊ > 0 be a fixed constant. We prove that S admits a (2 + ∊)-spanner with O(n log n) edges with respect to the geodesic distance. This is the first spanner with constant spanning ratio and a near-linear number of edges for points on a terrain. On our way to this result, we prove that any set of n weighted points in ℝd admits an additively weighted (2 + ∊)-spanner with O(n) edges; this improves the previously best known bound on the spanning ratio (which was 5 + ∊), and almost matches the lower bound.