2011-09-01

# Geometric spanners for weighted point sets

## Publication

### Publication

*Algorithmica , Volume 61 - Issue 1 p. 207- 225*

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: d ω(p,q)= 0 if p = Q, {w}(p)+ d(p,q)+ w(q) if p ≠ q qWe 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-ε.

Additional Metadata | |
---|---|

Keywords | Computational geometry, Doubling dimension, Geodesic metric, Geometric spanners, Semi-separated pair decomposition, Well-separated pair decomposition |

Persistent URL | dx.doi.org/10.1007/s00453-010-9465-2 |

Journal | Algorithmica |

Citation |
Abam, M.A. (Mohammad Ali), De Berg, M. (Mark), Farshi, M. (Mohammad), Gudmundsson, J. (Joachim), & Smid, M. (2011). Geometric spanners for weighted point sets. In
Algorithmica (Vol. 61, pp. 207–225). doi:10.1007/s00453-010-9465-2 |