caa a22 4500 445805064 CHVBK 20180317145154.0 cr unu---uuuuu 170323e20110901xx s 000 0 eng 10.1007/s00453-010-9465-2 doi (NATIONALLICENCE)springer-10.1007/s00453-010-9465-2 Geometric Spanners for Weighted Point Sets [Elektronische Daten] [Mohammad Abam, Mark de Berg, Mohammad Farshi, Joachim Gudmundsson, Michiel Smid] Let (S,d) be a finite metric space, where each element p∈S has a non-negative weight w (p). We study spanners for the set S with respect to the following weighted distance function: $$\mathbf{d}_{\omega}(p,q)=\left\{\begin{array}{ll}0&\mbox{ if $p=q$,}\\ \operatorname {w}(p)+\mathbf{d}(p,q)+ \operatorname {w}(q)&\mbox{ if $p\neq q$.}\end{array}\right.$$ We present a general method for turning spanners with respect to the d-metric into spanners with respect to the d ω-metric. For any given ε>0, we can apply our method to obtain (5+ε)-spanners with a linear number of edges for three cases: points in Euclidean space ℝd, points in spaces of bounded doubling dimension, and points on the boundary of a convex body in ℝd where d is the geodesic distance function. We also describe an alternative method that leads to (2+ε)-spanners for weighted point points in ℝd and for points on the boundary of a convex body inℝd. The number of edges in these spanners is O(nlog n). This bound on the stretch factor is nearly optimal: in any finite metric space and for any ε>0, it is possible to assign weights to the elements such that any non-complete graph has stretch factor larger than 2−ε. The Author(s), 2010 Computational geometry nationallicence Geometric spanners nationallicence Doubling dimension nationallicence Well-separated pair decomposition nationallicence Semi-separated pair decomposition nationallicence Geodesic metric nationallicence Abam Mohammad Department of Computer Science, Technische Universität Dortmund, Dortmund, Germany aut de Berg Mark Department of Computer Science, TU Eindhoven, Eindhoven, The Netherlands aut Farshi Mohammad Department of Computer Science, Yazd University, Yazd, Iran aut Gudmundsson Joachim NICTA, Sydney, Australia aut Smid Michiel School of Computer Science, Carleton University, K1S 5B6, Ottawa, ON, Canada aut Algorithmica Springer-Verlag 61/1(2011-09-01), 207-225 0178-4617 61:1<207 2011 61 453 https://doi.org/10.1007/s00453-010-9465-2 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/s00453-010-9465-2 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Abam Mohammad Department of Computer Science, Technische Universität Dortmund, Dortmund, Germany aut NATIONALLICENCE 700 1- de Berg Mark Department of Computer Science, TU Eindhoven, Eindhoven, The Netherlands aut NATIONALLICENCE 700 1- Farshi Mohammad Department of Computer Science, Yazd University, Yazd, Iran aut NATIONALLICENCE 700 1- Gudmundsson Joachim NICTA, Sydney, Australia aut NATIONALLICENCE 700 1- Smid Michiel School of Computer Science, Carleton University, K1S 5B6, Ottawa, ON, Canada aut NATIONALLICENCE 773 0- Algorithmica Springer-Verlag 61/1(2011-09-01), 207-225 0178-4617 61:1<207 2011 61 453 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer