Optimally sparse spanners in 3-dimensional Euclidean space
Gautam Das, Paul J. Heffernan, Giri Narasimhan · 1993
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 ttimes 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(MST), where MST is a minimum spanning tree of V.