Geometric spanners for weighted point sets

Public Deposited
Resource Type
Creator
Abstract
  • 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 weighted distance function d w , where d w (p,q) is w(p)+d(p,q)+wq if p≠q and 0 otherwise. We present a general method for turning spanners with respect to the d-metric into spanners with respect to the d w -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 points in ℝ d and for points on the boundary of a convex body in ℝ d . The number of edges in these spanners is O(nlogn). 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-ε.

Language
Publisher
Identifier
Citation
  • Ali Abam, M. (Mohammad), De Berg, M. (Mark), Farshi, M. (Mohammad), Gudmundsson, J. (Joachim), & Smid, M. (2009). Geometric spanners for weighted point sets. doi:10.1007/978-3-642-04128-0_17
Date Created
  • 2009-11-02

Relations

In Collection:

Items