Let V be a set of n points in 3-dimensional Euclidean space. A subgraph of the complete Euclidean graph is a t-spanner if for any u and v in V, the length of the shortest path from u to v in the spanner is at most t times d(u, v). We show that for any t > 1, a greedy algorithm produces a t-spanner with O(n) edges, and total edge weight O(1)·wt(M ST), where M ST is a minimum spanning tree of V.
