20110901
Spanners of additively weighted point sets
Publication
Publication
Journal of Discrete Algorithms , Volume 9  Issue 3 p. 287 298
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 (pi,ri) and (pj,rj) is defined as pipjrirj. We show that in the case where all ri are positive numbers and pi pj≥ri+rj 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 a spanning ratio bounded by a constant. The straightline 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 straightline embedding that also has a spanning ratio bounded by a constant in O(nlogn) time.
Additional Metadata  

, ,  
doi.org/10.1016/j.jda.2011.03.001  
Journal of Discrete Algorithms  
Organisation  School of Computer Science 
Bose, P, Carmi, P. (Paz), & Couture, M. (Mathieu). (2011). Spanners of additively weighted point sets. In Journal of Discrete Algorithms (Vol. 9, pp. 287–298). doi:10.1016/j.jda.2011.03.001
