Bounded Degree Planar Geometric Spanners

Given a set $P$ of $n$ points in the plane, we show how to compute in $O(n \log n)$ time a subgraph of their Delaunay triangulation that has maximum degree 7 and is a strong planar $t$-spanner of $P$ with $t =(1+ \sqrt{2})^2 *δ$, where $δ$ is the spanning ratio of the Delaunay triangulation. Furthermore, given a Delaunay triangulation, we show a distributed algorithm that computes the same bounded degree planar spanner in O(n) time.

No reviews yet.

No comments yet.