@article {
author = {Bakhshesh, D. and Farshi, M.},
title = {A lower bound on the stretch factor of Yao graph Y4},
journal = {Scientia Iranica},
volume = {29},
number = {6},
pages = {3244-3248},
year = {2022},
publisher = {Sharif University of Technology},
issn = {1026-3098},
eissn = {2345-3605},
doi = {10.24200/sci.2022.58892.5950},
abstract = {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).},
keywords = {$t$-spanner,Yao graph,Theta-graph,Lower bound},
url = {https://scientiairanica.sharif.edu/article_22846.html},
eprint = {https://scientiairanica.sharif.edu/article_22846_8a7779991e57bfbf6863842890b3ca59.pdf}
}