论文标题
在存在多边形障碍的情况下有限度跨度
Bounded-Degree Spanners in the Presence of Polygonal Obstacles
论文作者
论文摘要
让$ v $是飞机上的一组有限的顶点，而$ s $是有限的多边形障碍，其中$ s $的顶点在$ v $中。我们展示了如何相对于$ s $构建$ V $可见度图的$ 2 $ spanner。由于该图具有无界度，我们将其以三个易于遵循的步骤进行修改，以便将该度限制为$ 7 $，以略微增加跨度比为6的成本。
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.
