Bounded-Degree Spanners in the Presence of Polygonal Obstacles

09/15/2020

∙

by   André van Renssen, et al.

∙

0

∙

share

Let V be a finite set of vertices in the plane and S be a finite set of polygonal obstacles, where the vertices of S are in V. We show how to construct a plane 2-spanner of the visibility graph of V with respect to S. As this graph can have unbounded degree, we modify it in three easy-to-follow steps, in order to bound the degree to 7 at the cost of slightly increasing the spanning ratio to 6.