%0 Journal Article
%T A lower bound on the stretch factor of Yao graph Y4
%J Scientia Iranica
%I Sharif University of Technology
%Z 1026-3098
%A Bakhshesh, D.
%A Farshi, M.
%D 2022
%\ 12/01/2022
%V 29
%N 6
%P 3244-3248
%! A lower bound on the stretch factor of Yao graph Y4
%K $t$-spanner
%K Yao graph
%K Theta-graph
%K Lower bound
%R 10.24200/sci.2022.58892.5950
%X 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).
%U https://scientiairanica.sharif.edu/article_22846_8a7779991e57bfbf6863842890b3ca59.pdf