2017/04/12 by Bose, Prosenjit, Fagerberg, Rolf, van Renssen, André +1
#Computational Geometry (cs.CG) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.1704.03596
Let P be a finite set of points in the plane and S a set of non-crossing line segments with endpoints in P. The visibility graph of P with respect to S, denoted Vis(P,S), has vertex set P and an edge for each pair of vertices u,v in P for which no line segment of S properly intersects uv. We show that the constrained half-θ6-graph (which is identical to the constrained Delaunay graph whose empty visible region is an equilateral triangle) is a plane 2-spanner of Vis(P,S). We then show how to construct a plane 6-spanner of Vis(P,S) with maximum degree 6+c, where c is the maximum number of segments of S incident to a vertex.