2016
14
1
19
0
https://jcse.ir/article/25
Improving Space and Time Complexity of the Gap-Greedy Spanner Algorithm
0
Let S be a set of n points in and G be a geometric graph with vertex set S. For a fixed real number t 1, G is called a t-spanner of S if, for all pairs of vertices u, v S, the shortest path in G between u and v is no longer than t|uv|, where |uv| is the Euclidean distance between u and v. In this paper, we present an algorithm to construct the gap-greedy spanner that takes O n time and O n space, and another variant of this algorithm that takes O n time and O n space. We also improve the (theoretical) dilation of the gap-greedy spanner. Moreover, we present some other O n time algorithms to construct the gap-greedy spanner and compare their time complexity with the gap-greedy algorithm in practice. Furthermore, we experimentally compare the running time and some geometric properties of the gap-greedy spanner with the greedy spanner.
1
10
Davood
Bakhshesh
ایران
Mohammad
Farshi
ایران
Geometric Spanners
Gap-Greedy Spanner
Well-Separated Pair Decomposition
Greedy Spanner
http://jcse.ir/ow_userfiles/plugins/base/attachments/5bf26e3f9a6f5_5bf26e3f9a453.pdf
Computer Society of Iran
Journal on Computer Science and Engineering (JCSE)
14
1