2010/03/25 by Carmi, Paz, Chaitman, Lilach
#Computational Geometry (cs.CG) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.1003.4963
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+ √(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.