Spanners of additively weighted point sets
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 non-intersecting 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 face-dual 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.
Bose, P, Carmi, P. (Paz), & Couture, M. (Mathieu). (2008). Spanners of additively weighted point sets. doi:10.1007/978-3-540-69903-3_33