TY - CONF
T1 - Randomized and deterministic algorithms for geometric spanners of small diameter
T2 - Foundations of Computer Science, 1994 Proceedings., 35th Annual Symposium on
Y1 - 1994
A1 - Arya,S.
A1 - Mount, Dave
A1 - Smid,M.
KW - computational geometry
KW - deletions
KW - deterministic algorithms
KW - directed graph
KW - directed graphs
KW - geometric spanners
KW - insertions
KW - randomised algorithms
KW - randomized algorithms
AB - Let S be a set of n points in IR^{d} and let t gt;1 be a real number. A t-spanner for S is a directed graph having the points of S as its vertices, such that for any pair p and q of points there is a path from p to q of length at most t times the Euclidean distance between p and p. Such a path is called a t-spanner path. The spanner diameter of such a spanner is defined as the smallest integer D such that for any pair p and q of points there is a t-spanner path from p to q containing at most D edges. Randomized and deterministic algorithms are given for constructing t-spanners consisting of O(n) edges and having O(log n) diameter. Also, it is shown how to maintain the randomized t-spanner under random insertions and deletions. Previously, no results were known for spanners with low spanner diameter and for maintaining spanners under insertions and deletions
JA - Foundations of Computer Science, 1994 Proceedings., 35th Annual Symposium on
M3 - 10.1109/SFCS.1994.365722
ER -