Spanners of additively weighted point sets |
| |
Authors: | Prosenjit Bose Paz Carmi Mathieu Couture |
| |
Affiliation: | School of Computer Science, Carleton University, Herzberg Building, 1125 Colonel By Drive, Ottawa, Ontario, Canada |
| |
Abstract: | 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 a spanning ratio bounded by a constant. 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 straight-line embedding that also has a spanning ratio bounded by a constant in time. |
| |
Keywords: | Geometric spanners Yao-graph Delaunay triangulation |
本文献已被 ScienceDirect 等数据库收录! |
|