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.
The @cite_18 of a finite set of points @math is a partition of the plane into @math regions such that each region contains exactly those points having the same nearest neighbor in @math . The points in @math are also called . It is well known that the Voronoi diagram of a set of points is the face dual of the Delaunay graph of that set of points @cite_18 , i.e. two points have adjacent Voronoi regions if and only if they share an edge in the Delaunay graph (see Figure ).
@cite_18
2149906774
This introduction to computational geometry focuses on algorithms. Motivation is provided from the application areas as all techniques are related to particular applications in robotics, graphics, CAD CAM, and geographic information systems. Modern insights in computational geometry are used to provide solutions that are both efficient and easy to understand and implement.