# 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

In Collection:
{"ft_lang_label":"__label__en","ft_lang_prob":0.77207184,"math_prob":0.95810527,"size":1596,"snap":"2023-14-2023-23","text_gpt3_token_len":441,"char_repetition_ratio":0.11809045,"word_repetition_ratio":0.06818182,"special_character_ratio":0.2650376,"punctuation_ratio":0.11801242,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.9748939,"pos_list":[0],"im_url_duplicate_count":[null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2023-05-28T22:02:26Z\",\"WARC-Record-ID\":\"<urn:uuid:89a7aad3-fc67-4dc7-ab27-15808a498f81>\",\"Content-Length\":\"23819\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:0539a7c7-d3b8-4a05-a5bb-d59cd7f712f9>\",\"WARC-Concurrent-To\":\"<urn:uuid:78411aea-e842-45df-9ad1-9af216ea6529>\",\"WARC-IP-Address\":\"134.117.10.38\",\"WARC-Target-URI\":\"https://repository.library.carleton.ca/concern/research_works/1j92g7448\",\"WARC-Payload-Digest\":\"sha1:I37NXLJDJ4R5UMGIP6CFM2DBX4EZ7GBM\",\"WARC-Block-Digest\":\"sha1:ZA74RBTBCPPWOKKNRP7XYW45QVJNV5G2\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2023/CC-MAIN-2023-23/CC-MAIN-2023-23_segments_1685224644571.22_warc_CC-MAIN-20230528214404-20230529004404-00580.warc.gz\"}"}