TY - JOUR
ID - 22846
TI - A lower bound on the stretch factor of Yao graph Y4
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 - Combinatorial and Geometric Algorithms Lab., Department of Mathematical Sciences, Yazd University, P.O. Box 89195-747,
Yazd, Iran
Y1 - 2022
PY - 2022
VL - 29
IS - 6
SP - 3244
EP - 3248
KW - $t$-spanner
KW - Yao graph
KW - Theta-graph
KW - Lower bound
DO - 10.24200/sci.2022.58892.5950
N2 - One of the most popular graphs in computational geometry is Yao graphs, denoted by $Y_k$, For every point set $S$ in the plane and an integer $k\geq 2$, the Yao graph $Y_k$ is constructed as follows. Around each point $p\in S$, the plane is partitioned into $k$ regular cones with the apex at $p$. The set of all these cones is denoted by ${\cal C}_p$. Then, for each cone $C\in {\cal C}_p$, an edge $(p,r)$ is added to $Y_k$, where $r$ is a closest point in $C$ to $p$. In this paper, we provide a lower bound of 3.8285 for the stretch factor of $Y_4$. This partially solves an open problem posed by Barba et al. (L.~Barba et al., New and improved spanning ratios for Yao graphs. Journal of computational geometry}, 6(2):19--53, 2015).
UR - https://scientiairanica.sharif.edu/article_22846.html
L1 - https://scientiairanica.sharif.edu/article_22846_8a7779991e57bfbf6863842890b3ca59.pdf
ER -