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.
Let @math be a real number. Two set of points @math and @math in @math are if there exists two @math -dimensional balls @math and @math of same radius @math respectively containing the bounding boxes of @math and @math such that the distance between @math and @math is greater than or equal to @math . The distance between @math and @math is defined as the distance between their centers minus @math . A @cite_3 @cite_29 is a set of unordered pairs @math of subsets of @math that are well-separated with respect to @math with the additional property that for every two points @math there is exactly one pair @math such that @math and @math . showed that for @math , every point set admits a WSPD with separation ratio @math of @math size that can be computed in @math time. Choosing one edge per pair allows to construct a @math -spanner that has @math size with @math .
@cite_29 @cite_3
1505970908 2054011861
Part I. Introduction: 1. Introduction 2. Algorithms and graphs 3. The algebraic computation-tree model Part II. Spanners Based on Simplical Cones: 4. Spanners based on the Q-graph 5. Cones in higher dimensional space and Q-graphs 6. Geometric analysis: the gap property 7. The gap-greedy algorithm 8. Enumerating distances using spanners of bounded degree Part III. The Well Separated Pair Decomposition and its Applications: 9. The well-separated pair decomposition 10. Applications of well-separated pairs 11. The Dumbbell theorem 12. Shortcutting trees and spanners with low spanner diameter 13. Approximating the stretch factor of Euclidean graphs Part IV. The Path Greedy Algorithm: 14. Geometric analysis: the leapfrog property 15. The path-greedy algorithm Part V. Further Results and Applications: 16. The distance range hierarchy 17. Approximating shortest paths in spanners 18. Fault-tolerant spanners 19. Designing approximation algorithms with spanners 20. Further results and open problems. We define the notion of a well-separated pair decomposition of points in d -dimensional space. We then develop efficient sequential and parallel algorithms for computing such a decomposition. We apply the resulting decomposition to the efficient computation of k -nearest neighbors and n -body potential fields.