TY - JOUR
ID - 22416
TI - A degree 3 plane 5.19-spanner for points in convex position
JO - Scientia Iranica
JA - SCI
LA - en
SN - 1026-3098
AU - Bakhshesh, D.
AU - Farshi, M.
AD - Department of Computer Science, University of Bojnord, Bojnord, Iran
AD - Department of Mathematical Sciences, Combinatorial and Geometric Algorithms Lab., Yazd University, Yazd, P.O. Box
89195-741, Iran
Y1 - 2021
PY - 2021
VL - 28
IS - 6
SP - 3324
EP - 3331
KW - Plane spanner
KW - Stretch factor
KW - greedy spanner
KW - Computational geometry
DO - 10.24200/sci.2021.56576.4796
N2 - Let $S$ be a set of $n$ points in the plane that is in convex position. In this paper, using the well-known path-greedy spanner algorithm, we present an algorithm that constructs a plane $\frac{3+4\pi}{3}$-spanner $G$ of degree 3 on the point set $S$. Recently, Biniaz et al. ({\it Towards plane spanners of degree 3, Journal of Computational Geometry, 8 (1), 2017}) have proposed an algorithm that constructs a degree 3 plane $\frac{3+4\pi}{3}$-spanner $G'$ for $S$. We show that there is no upper bound with a constant factor on the total weight of $G'$, but the total weight of $G$ is asymptotically equal to the total weight of the minimum spanning tree of $S$.
UR - https://scientiairanica.sharif.edu/article_22416.html
L1 - https://scientiairanica.sharif.edu/article_22416_4b0d15eb08ab41c714ba9aecec88cf3a.pdf
ER -