TY - JOUR
ID - 81307
TI - $alpha$-Gap Greedy Spanner
JO - Journal of Algorithms and Computation
JA - JAC
LA - en
SN - 2476-2776
AU - Salami, Hosein
AU - Nouri Baygi, Mostafa
AD - Department of Computer Engineering, Ferdowsi University of Mashhad
AD - Department of Computer Engineering, Ferdowsi University of Mashhad, Mashhad, Iran
Y1 - 2021
PY - 2021
VL - 53
IS - 1
SP - 41
EP - 60
KW - computational geometry
KW - geometric spanners
KW - gap greedy spanner
KW - construction algorithms
KW - algorithm complexity
DO - 10.22059/jac.2021.81307
N2 - In this paper, we have introduced a new geometric spanner called $alpha$-Gap greedy spanner, which is a parametric approximation of the well-known Gap-greedy spanner. We will show theoretically and experimentally that this spanner is similar to the Gap-greedy spanner in terms of qualitative features such as weight and maximum degree of vertices. %Wehave shown that this spanner can be computed in $O(n^2 log n)$ time with$O(n)$ space, and $O(n log n)$ expected time on the set of points placedrandomly in a unit square.Two algorithms have been proposed with running time $O(n^2 log n)$ for constructing the $alpha$-Gap greedy spanner. Space complexity of the first algorithm is $O(n^2)$, but it is reduced to $O(n)$ in the second one. %The proposed algorithms have a parameter, called $alpha$, by which the similarity of the $alpha$-Gap greedy spanner to the Gap-greedy spanner, in terms of quality features mentioned above, can be determined. Also, we have shown on the points placed randomly in a unit square, the $alpha$-Gap greedy spanner can be constructed in the expected $O(n log n)$ time.
UR - https://jac.ut.ac.ir/article_81307.html
L1 - https://jac.ut.ac.ir/article_81307_669c0a0df2c0484e4332a6e5ff9041b6.pdf
ER -