A degree 3 plane 5.19-spanner for points in convex position

Document Type : Article


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

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


Let $S$ be a set of $n$ points in the plane that is in convex position. In this paper, using the well-known path-greedy spanner algorithm, we present an algorithm that constructs a plane $\frac{3+4\pi}{3}$-spanner $G$ of degree 3 on the point set $S$. Recently, Biniaz et al. ({\it Towards plane spanners of degree 3, Journal of Computational Geometry, 8 (1), 2017}) have proposed an algorithm that constructs a degree 3 plane $\frac{3+4\pi}{3}$-spanner $G'$ for $S$. We show that there is no upper bound with a constant factor on the total weight of $G'$, but the total weight of $G$ is asymptotically equal to the total weight of the minimum spanning tree of $S$.


1. Narasimhan, G. and Smid, M., Geometric Spanner Networks, Cambridge University Press (2007).
2. Abam, M.A., Baharifard, F., Borouny, M., and Zarrabi- Zadeh, H. "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., De Carufel, J.-L., Damian, M., Fagerberg, R., Farshi, M., van Renssen, A.,  aslakian, P., and Verdonschot, S. "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. 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).
10. Kanj, I., Perkovic, L., and Turkoglu, D. "Degree four plane spanners: Simpler and better", Journal of Computational Geometry, 8(2), pp. 3-31 (2017).
11. Das, G. and Heffernan, P.J. "Constructing degree-3 spanners with other sparseness properties", International Journal of Foundations of Computer Science, 07(02), pp. 121-135 (1996).
12. Bose, P., Gudmundsson, J., and Smid, M. "Constructing plane spanners of bounded degree and low weight", Algorithmica, 42(3), pp. 249-264 (2005).
13. Li, X.-Y. and Wang, Y. "Efficient construction of low weighted bounded degree planar spanner", Int. J. Comput. Geom. Ap, 14(01n02), pp. 69-84 (2004).
14. Bose, P., Smid, M., and Xu, D. "Delaunay and diamond triangulations contain spanners of bounded degree", Int. J. Comput. Geom. Ap, 19(02), pp. 119- 140 (2009).
15. Perkovic, L. and Kanj, I.A. "On geometric spanners of Euclidean and unit disk graphs", In Proc. 25th Int. Sympos. on Theoretical Aspects of Computer Science, pp. 409-420 (2008).
16. Bonichon, N., Gavoille, C., Hanusse, N., and Perkovic, L. "Plane spanners of maximum degree six", In Automata, Languages and Programming, S. Abramsky, C. Gavoille, C. Kirchner, F. Meyer aufder Heide, and P.G. Spirakis, Eds., Berlin, Heidelberg, Springer Berlin Heidelberg, pp. 19-30 (2010).
17. Bose, P., Carmi, P., and Chaitman-Yerushalmi, L. "On bounded degree plane strong geometric spanners", Journal of Discrete Algorithms, 15, pp. 16-31 (2012).
18. Bonichon, N., Kanj, I., Perkovic, L., and Xia, G. "There are plane spanners of degree 4 and moderate stretch factor", Discrete Comput. Geom., 53(3), pp. 514-546 (2015).
19. Biniaz, A., Bose, P., De Carufel, J.-L., Gavoille, C., Maheshwari, A., and Smid, M. "Towards plane spanners  of degree 3", Journal of Computational Geometry, 8(1), pp. 11-31 (2017).
20. Biniaz, A. and Smid, M., Personal Communication (2019).
21. Bose, P., Carmi, P., Farshi, M., Maheshwari, A., and Smid, M. "Computing the greedy spanner in near-quadratic time", Algorithmica, 58(3), pp. 711-729 (2010).
22. Benson, R., Euclidean Gometry and Convexity, McGraw-Hill (1966).
23. Smid, M. "Errata for the book geometric spanner networks", (2013). http://people.scs.carleton.ca/ michiel/SpannerBook/
24. Deineko, V.G., Hoffmann, M., Okamoto, Y., and Woeginger, G.J. "The traveling salesman problem with few inner points", Oper. Res. Lett., 34(1), pp. 106-110 (2006).