Bounded Degree Planar Geometric Spanners

Abstract

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\ast \delta$, where $\delta$ 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.