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.
d차원 공간상에 주어진 점들에 대한 좋은 속성 가진 네트워크를 구성하는 것은 중요하다. t스패너는 스트래치 팩터라 불리우는 속성을 만족하는 그래프를 의미한다. 좀 더 정확하게 d차원 공간상에 S 라는 점들의 집합이 주어진 경우 만약 S에 포함된 임의의 서로 다른 두 점 p와 q에 대해 그래프 G가 p와 q 사이의 유클리드 거리보다 t배 짧은 길이의 최단 경로를 가지면, 이 그래프 G(S,E)를 t스패너라 정의한다.
지난 수십 년 동안 t스패너를 구성하기 위한 다양한 기법들이 고안 되었고, 이렇게 생성된 t스패너들은 다양한 다른 속성들을 가지고 있기도 하다. 이 논문에서는 다른 추가 속성들을 가지는 t스패너를 생성하는 단시간 기법을 소개하고, 실험들을 통해서 실제로 이 알고리즘이 얼마나 효과적인지를 보인다.
