2008/01/25 by Prosenjit Bose, Bose, Prosenjit, Paz Carmi +3
Computer Science · Mathematics · #Computational Geometry (cs.CG) #Computational Geometry and Mesh Generation #Digital Image Processing Techniques #FOS: Computer and information sciences #Fixed Point Theorems Analysis #cs.CG
paper · pdf · doi:10.48550/arxiv.0801.4013
arxiv created 2008/01/25 · openalex publication_date 2008/01/25 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 |pipj|-ri-rj. We show that in the case where all ri are positive numbers and |pipj|≥ ri+rj 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. We show how to compute a plane embedding that also has a constant spanning ratio.