Sharif University of TechnologyScientia Iranica1026-309829620221201A lower bound on the stretch factor of Yao graph Y4324432482284610.24200/sci.2022.58892.5950END. BakhsheshDepartment of Computer Science, University of Bojnord, Bojnord, IranM. FarshiCombinatorial and Geometric Algorithms Lab., Department of Mathematical Sciences, Yazd University, P.O. Box 89195-747,
Yazd, IranJournal Article20210819One 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).https://scientiairanica.sharif.edu/article_22846_8a7779991e57bfbf6863842890b3ca59.pdf