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

Let S be a set of n points in the plane that is in convex position. Using the well-known path-greedy spanner algorithm, this study presents an algorithm that constructs a plane 3+4- 3 -spanner G of degree 3 on the point set S. Recently, Biniaz et al. [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).] proposed an algorithm that constructs a degree 3 plane 3+4- 3 -spanner G0 for S. It was found that there was no upper bound with a constant factor in the total weight of G0, but the total weight of G was asymptotically equal to that of the minimum spanning tree of S. [ABSTRACT FROM AUTHOR]