arXiv Open Access 2020

Bounded-Degree Spanners in the Presence of Polygonal Obstacles

André van Renssen Gladys Wong

Lihat Sumber

Abstrak

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.

Topik & Kata Kunci

cs.CG

Penulis (2)

André van Renssen

Gladys Wong

Format Sitasi

APA MLA BibTeX

Renssen, A.v., Wong, G. (2020). Bounded-Degree Spanners in the Presence of Polygonal Obstacles. https://arxiv.org/abs/2009.06879

Akses Cepat

Lihat di Sumber

Informasi Jurnal

Tahun Terbit: 2020
Bahasa: en
Sumber Database: arXiv
Akses: Open Access ✓