CONSTRUCTING DEGREE-3 SPANNERS WITH OTHER SPARSENESS PROPERTIES

Let V be any set of n points in k-dimensional Euclidean space. A subgraph of the complete Euclidean graph is a t-spanner if for all u and υ in V, the length of the shortest path from u to υ in the spanner is at most t times the Euclidean distance between u and υ. We show that for any δ>1, there exists a t-spanner (where t is a constant that depends only on δ and k) with the following properties: its maximum degree is 3, it has at most n·δ edges, its total edge weight is at most O(1) times the weight of the minimum spanning tree of V, and it can be constructed in O(n log n) time. The constants implicit in the O-notation depend on δ and k.