Optimally sparse spanners in 3-dimensional Euclidean space
- 1 January 1993
- proceedings article
- Published by Association for Computing Machinery (ACM)
Abstract
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.Keywords
This publication has 0 references indexed in Scilit: