Bounded-degree spanners in the presence of polygonal obstacle

•We show how to construct a 2-spanner among polygonal obstacles.•We show how to construct a 6-spanner among polygonal obstacles of degree at most 15.•We show how to construct a 6-spanner among polygonal obstacles of degree at most 10.•We show how to construct a 6-spanner among polygonal obstacles of...

Full description

Saved in:
Bibliographic Details
Published in:Theoretical computer science 2021-01, Vol.854, p.159-173
Main Authors: van Renssen, André, Wong, Gladys
Format: Article
Language:English
Subjects:
Bounded-degree
Polygonal obstacles
Spanners
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:•We show how to construct a 2-spanner among polygonal obstacles.•We show how to construct a 6-spanner among polygonal obstacles of degree at most 15.•We show how to construct a 6-spanner among polygonal obstacles of degree at most 10.•We show how to construct a 6-spanner among polygonal obstacles of degree at most 7. 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.
ISSN:0304-3975
1879-2294
DOI:10.1016/j.tcs.2020.12.024