Geometric Spanner Algorithms in Euclidean Space with Experiments

Abstract

For a given set of points in Rd, it is desirable to construct a network with good properties. A t-spanner is a network satisfying a property, called the stretch factor. Let S be a set of n points in Rd. A graph G(S,E) is a t-spanner for S if for any two points p and q in S the shortest-path distance in G between p and q is less than or equal to |pq|, where |pq| denotes the Euclidean distance between p and q.Various algorithms have been invented for the last few decades to construct a t-spanner, that even satisfies additional properties. In this thesis, we introduce a way to construct a t-spanner that improves the computation time of state-of-the-art technique, and we prove some additional properties of the t- spanner. We show that how the t-spanner achieves some desirable properties of a network in practice through the experimental study.