GEODESIC SPANNERS FOR POINTS ON A POLYHEDRAL TERRAIN.

Let S be a set of n points on a polyhedral terrain T in R³, 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 \BbbR 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. [ABSTRACT FROM AUTHOR]