We study the problem of computing geometric spanners for (additively) weighted point sets. A weighted point set is a set of pairs @math where @math is a point in the plane and @math is a real number. The distance between two points @math and @math is defined as @math . We show that in the case where all @math are positive numbers and @math for all @math (in which case the points can be seen as non-intersecting disks in the plane), a variant of the Yao graph is a @math -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.
Another graph that has been looked at is the . In that case, points are assigned a unique color (which may be thought of as a positive integer) between 1 and @math , and there is an edge between two points if and only if they are assigned different colors. Bose al @cite_21 showed that the WSPD can be adapted to compute a @math -spanner of that graph that has @math edges for arbitrary values of @math strictly greater than 5.
@cite_21
1780187217
We address the following problem: Given a complete @math -partite geometric graph @math whose vertex set is a set of @math points in @math , compute a spanner of @math that has a “small” stretch factor and “few” edges. We present two algorithms for this problem. The first algorithm computes a @math -spanner of @math with @math edges in @math time. The second algorithm computes a @math -spanner of @math with @math edges in @math time. The latter result is optimal: We show that for any @math , spanners with @math edges and stretch factor less than 3 do not exist for all complete @math -partite geometric graphs.