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.
For spanners of arbitrary geometric graphs, much less is known. Alth "o fer @cite_26 have shown that for any @math , every weighted graph @math with @math vertices contains a subgraph with @math edges, which is a @math -spanner of @math . Observe that this result holds for any weighted graph; in particular, it is valid for any geometric graph. For geometric graphs, a lower bound was given by Gudmundsson and Smid @cite_6 : They proved that for every real number @math with @math , there exists a geometric graph @math with @math vertices, such that every @math -spanner of @math contains @math edges. Thus, if we are looking for spanners with @math edges of arbitrary geometric graphs, then the best spanning ratio we can obtain is @math .
@cite_26 @cite_6
1496182974 2951859740 2809995963 2227069303
Given a connected geometric graph G, we consider the problem of constructing a t-spanner of G having the minimum number of edges. We prove that for every t with @math , there exists a connected geometric graph G with n vertices, such that every t-spanner of G contains Ω( n1+1 t ) edges. This bound almost matches the known upper bound, which states that every connected weighted graph with n vertices contains a t-spanner with O(tn1+2 (t+1)) edges. We also prove that the problem of deciding whether a given geometric graph contains a t-spanner with at most K edges is NP-hard. Previously, this NP-hardness result was only known for non-geometric graphs Given an undirected @math -node unweighted graph @math , a spanner with stretch function @math is a subgraph @math such that, if two nodes are at distance @math in @math , then they are at distance at most @math in @math . Spanners are very well studied in the literature. The typical goal is to construct the sparsest possible spanner for a given stretch function. In this paper we study pairwise spanners, where we require to approximate the @math - @math distance only for pairs @math in a given set @math . Such @math -spanners were studied before [Coppersmith,Elkin'05] only in the special case that @math is the identity function, i.e. distances between relevant pairs must be preserved exactly (a.k.a. pairwise preservers). Here we present pairwise spanners which are at the same time sparser than the best known preservers (on the same @math ) and of the best known spanners (with the same @math ). In more detail, for arbitrary @math , we show that there exists a @math -spanner of size @math with @math . Alternatively, for any @math , there exists a @math -spanner of size @math with @math . We also consider the relevant special case that there is a critical set of nodes @math , and we wish to approximate either the distances within nodes in @math or from nodes in @math to any other node. We show that there exists an @math -spanner of size @math with @math , and an @math -spanner of size @math with @math . All the mentioned pairwise spanners can be constructed in polynomial time. An (α,β)-spanner of an n-vertex graph G = (V,E) is a subgraph H of G satisfying that dist(u, v, H) ≤ α·dist(u, v, G) + β for every pair (u, v) ∈ V ×V, where dist(u,v,G′) denotes the distance between u and v in G′ ⊆ G. It is known that for every integer k ≥ 1, every graph G has a polynomially constructible (2k − 1,0)-spanner of size O(n 1 + 1 k ). This size-stretch bound is essentially optimal by the girth conjecture. Yet, it is important to note that any argument based on the girth only applies to adjacent vertices. It is therefore intriguing to ask if one can “bypass” the conjecture by settling for a multiplicative stretch of 2k − 1 only for neighboring vertex pairs, while maintaining a strictly better multiplicative stretch for the rest of the pairs. We answer this question in the affirmative and introduce the notion of k-hybrid spanners, in which non neighboring vertex pairs enjoy a multiplicative k stretch and the neighboring vertex pairs enjoy a multiplicative (2k − 1) stretch (hence, tight by the conjecture). We show that for every unweighted n-vertex graph G, there is a (polynomially constructible) k-hybrid spanner with O(k 2 ·n 1 + 1 k ) edges. This should be compared against the current best (α,β) spanner construction of [5] that obtains (k,k − 1) stretch with O(k ·n 1 + 1 k ) edges. An alternative natural approach to bypass the girth conjecture is to allow ourself to take care only of a subset of pairs S ×V for a given subset of vertices S ⊆ V referred to here as sources. Spanners in which the distances in S ×V are bounded are referred to as sourcewise spanners. Several constructions for this variant are provided (e.g., multiplicative sourcewise spanners, additive sourcewise spanners and more). A spanner is a sparse subgraph that approximately preserves the pairwise distances of the original graph. It is well known that there is a smooth tradeoff between the sparsity of a spanner and the quality of its approximation, so long as distance error is measured multiplicatively. A central open question in the field is to prove or disprove whether such a tradeoff exists also in the regime of additive error. That is, is it true that for all e>0, there is a constant ke such that every graph has a spanner on O(n1+e) edges that preserves its pairwise distances up to +ke? Previous lower bounds are consistent with a positive resolution to this question, while previous upper bounds exhibit the beginning of a tradeoff curve: all graphs have +2 spanners on O(n3 2) edges, +4 spanners on O(n7 5) edges, and +6 spanners on O(n4 3) edges. However, progress has mysteriously halted at the n4 3 bound, and despite significant effort from the community, the question has remained open for all 0 Our main result is a surprising negative resolution of the open question, even in a highly generalized setting. We show a new information theoretic incompressibility bound: there is no function that compresses graphs into O(n4 3 − e) bits so that distance information can be recovered within +no(1) error. As a special case of our theorem, we get a tight lower bound on the sparsity of additive spanners: the +6 spanner on O(n4 3) edges cannot be improved in the exponent, even if any subpolynomial amount of additive error is allowed. Our theorem implies new lower bounds for related objects as well; for example, the twenty-year-old +4 emulator on O(n4 3) edges also cannot be improved in the exponent unless the error allowance is polynomial. Central to our construction is a new type of graph product, which we call the Obstacle Product. Intuitively, it takes two graphs G,H and produces a new graph G H whose shortest paths structure looks locally like H but globally like G.