A lower bound on the stretch factor of Yao graph Y4

Document Type : Article

Authors

1 Department of Computer Science, University of Bojnord, Bojnord, Iran

2 Combinatorial and Geometric Algorithms Lab., Department of Mathematical Sciences, Yazd University, P.O. Box 89195-747, Yazd, Iran

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

References

References:
1. Narasimhan, G. and Smid, M., Geometric spanner networks, Cambridge University Press (2007).
2. Abam, M.A., Baharifard, F., Borouny, M., et al. "Fault-tolerant spanners in networks with symmetric directional antennas", Theor. Comput. Sci., 704, pp. 18-27 (2017).
3. Abam, M.A., De Berg, M., and Seraji, M.J.R. "Geodesic spanners for points on a polyhedral terrain", SIAM J. COMPUT., 48(6), pp. 1796-1810 (2019).
4. Abam, M.A. and Qafari, M.S. "Geometric spanner games", Theor. Comput. Sci., 795, pp. 398-407 (2019).
5. Bakhshesh, D., Barba, L., Bose, P., et al. "Continuous Yao graphs", Comp. Geom-Theor. App., 67, pp. 42-52 (2018).
6. Bakhshesh, D. and Farshi, M. "Angle-constrained spanners with angle at least π=3", Inform. Process. Lett., 120, pp. 44-46 (2017).
7. Bakhshesh, D. and Farshi, M. "Fault tolerancy of continuous Yao graph of angle less than 2π=5", Inform. Process. Lett., 148, pp. 13-18 (2019).
8. Bakhshesh, D. and Farshi, M. "(Weakly) Selfapproaching geometric graphs and spanners", Comp. Geom-Theor. App., 78, pp. 20-36 (2019).
9. Bakhshesh, D. and Farshi, M. "A degree 3 plane 5:19-spanner for points in convex position", Scientia Iranica, 28, pp. 3324-3331 (2021).
10. Iranfar, B. and Farshi, M. "On the expected weight of the theta graph on uncertain points", Journal of Algorithms and Computation, 52(1), pp. 163-174 (2020).
11. Flinchbaugh, B. and Jones, L. " Strong connectivity in directional nearest-neighbor graphs", Siam J Algebra DISCR., 2, pp. 461-463 (1981).
12. Yao, A.C.-C. "On constructing minimum spanning trees in k-dimensional spaces and related problems", Siam J Comput., 11, pp. 721-736 (1982).
13. Clarkson, K. "Approximation algorithms for shortest path motion planning", In Proc. 19th ACM Sympos. on Theory of Computing, pp. 56-65 (1987).
14. Keil, J.M. "Approximating the complete Euclidean graph", In Scandinavian Workshop on Algorithm Theory, pp. 208-213 (1988).
15. Althofer, I., Das, G., Dobkin, D., et al. "On sparse spanners of weighted graphs", Discrete Comput. Geom., 9, pp. 81-100 (1993).
16. Bose, P., Maheshwari, A., Narasimhan, G., et al. "Approximating geometric bottleneck shortest paths", Comp. Geom-Theor. App., 29, pp. 233-249 (2004). 
17. Bose, P., Damian, M., Doueb, K., et al. "π=2-angle Yao graphs are spanners", Int. J. Comput. Geom. Ap., 22, pp. 61-82 (2012).
18. Damian, M. and Raudonis, K. "Yao graphs span theta graphs", Discrete Mathematics, Algorithms and Applications, 4, p. 1250024 (2012).
19. Barba, L., Bose, P., Damian, M., et al. "New and improved spanning ratios for Yao graphs", Journal of Computational Geometry, 6, pp. 19-53 (2015).
20. Damian, M. and Nelavalli, N. "Improved bounds on the stretch factor of Y4", Comp. Geom-Theor. App., 62, pp. 14-24 (2017).
21. Barba, L., Bose, P., De Carufel, J.-L., et al. "On the stretch factor of the theta-4 graph", In Workshop on Algorithms and Data Structures, pp. 109-120 (2013).
22. Molla, N. M. El. "Yao spanners for wireless ad hoc networks", Master's thesis, Villanova University (2009).
Scientia Iranica
Volume 29, Issue 6 - Serial Number 6
Transactions on Computer Science & Engineering and Electrical Engineering (D)
November and December 2022
Pages 3244-3248

Files

History

  • Receive Date: 19 August 2021
  • Revise Date: 04 May 2022
  • Accept Date: 11 July 2022

Share

How to cite

Statistics