20081027
Spanners of additively weighted point sets
Publication
Publication
We study the problem of computing geometric spanners for (additively) weighted point sets. A weighted point set is a set of pairs (p,r) where p is a point in the plane and r is a real number. The distance between two points (p i ,r i ) and (p j ,r j ) is defined as p i p j ∈∈r i ∈∈r j . We show that in the case where all r i are positive numbers and p i p j  ≥ r i ∈+∈r j for all i,j (in which case the points can be seen as nonintersecting disks in the plane), a variant of the Yao graph is a (1∈+∈ε)spanner that has a linear number of edges. We also show that the Additively Weighted Delaunay graph (the facedual of the Additively Weighted Voronoi diagram) has constant spanning ratio. The straight line embedding of the Additively Weighted Delaunay graph may not be a plane graph. Given the Additively Weighted Delaunay graph, we show how to compute a plane embedding with a constant spanning ratio in O(nlogn) time.
Additional Metadata  

Persistent URL  dx.doi.org/10.1007/9783540699033_33 
Citation 
Bose, P, Carmi, P. (Paz), & Couture, M. (Mathieu). (2008). Spanners of additively weighted point sets. doi:10.1007/9783540699033_33
