optimally sparse spanners in 3-dimensional euclidean space
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(MST) , where MST is a minimum spanning tree of V .
spanner space point graph completeness shortest path greedy algorithm minimum spanning tree