Plane Bounded-Degree Spanners Among the Obstacles for the Points in Convex Position

Let S be a set of points in the plane that are in convex position. Let O be a set of simple polygonal obstacles whose vertices are in S. The visibility graph V is(S, O) is the graph which is obtained from the complete graph of S by removing all edges intersecting some obstacle of O. In this paper, we show that there is a plane 5.19-spanner of the visibility graph V is(S, O) of degree at most 6. Moreover, we show that there is a plane 1.88-spanner of the visibility graph V is(S, O). These improve the stretch factor and the maximum degree of the previ-ous results by A. van Renssen and G. Wong (Theoretical Computer Science, 2021) in the context of points in con-vex position.