Geometric spanners for weighted point sets

M.A. Abam, M.T. Berg, de, M. Farshi, J. Gudmundsson, M.H.M. Smid

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

1 Citation (Scopus)

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 e>¿0, we can apply our method to obtain (5¿+¿e)-spanners with a linear number of edges for three cases: points in Euclidean space R d , points in spaces of bounded doubling dimension, and points on the boundary of a convex body in R d where d is the geodesic distance function. We also describe an alternative method that leads to (2¿+¿e)-spanners for points in R d and for points on the boundary of a convex body in R 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 e>¿0, it is possible to assign weights to the elements such that any non-complete graph has stretch factor larger than 2¿-¿e.
Original languageEnglish
Title of host publicationAlgorithms - ESA 2009 (17th Annual European Symposium, Copenhagen, Denmark, September 7-9, 2009. Proceedings)
EditorsA. Fiat, P. Sanders
Place of PublicationBerlin
PublisherSpringer
Pages190-202
ISBN (Print)978-3-642-04127-3
DOIs
Publication statusPublished - 2009

Publication series

NameLecture Notes in Computer Science
Volume5757
ISSN (Print)0302-9743

Fingerprint Dive into the research topics of 'Geometric spanners for weighted point sets'. Together they form a unique fingerprint.

  • Cite this

    Abam, M. A., Berg, de, M. T., Farshi, M., Gudmundsson, J., & Smid, M. H. M. (2009). Geometric spanners for weighted point sets. In A. Fiat, & P. Sanders (Eds.), Algorithms - ESA 2009 (17th Annual European Symposium, Copenhagen, Denmark, September 7-9, 2009. Proceedings) (pp. 190-202). (Lecture Notes in Computer Science; Vol. 5757). Berlin: Springer. https://doi.org/10.1007/978-3-642-04128-0_17