A degree 3 plane 5.19-spanner for points in convex position
Author(s):
Article Type:
Research/Original Article (دارای رتبه معتبر)
Abstract:
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+4pi}{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+4pi}{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$.
Keywords:
Language:
English
Published:
Scientia Iranica, Volume:28 Issue: 6, Nov-Dec 2021
Pages:
3324 to 3331
https://www.magiran.com/p2375575
سامانه نویسندگان
مقالات دیگری از این نویسنده (گان)
-
Angle-monotonicity of theta-graphs for points in convex position
D. Bakhshesh *, M. Farshi
Scientia Iranica, Nov-Dec 2023 -
A lower bound on the stretch factor of Yao graph Y4
D. Bakhshesh *, M. Farshi
Scientia Iranica, Nov-Dec 2022