Vertex Fault-Tolerant Geometric Spanners for Weighted Points

DOI10.1142/S021819592250008XzbMATH Open1523.68127arXiv2011.03354OpenAlexW4311159574MaRDI QIDQ6173263FDOQ6173263

Authors: Sukanya Bhattacharjee, Rajasekhar Inkulu 

Publication date: 21 July 2023

Published in: International Journal of Computational Geometry & Applications (Search for Journal in Brave)

Abstract: Given a set S of n points, a weight function w to associate a non-negative weight to each point in S, a positive integer k ge 1, and a real number epsilon > 0, we present algorithms for computing a spanner network G(S, E) for the metric space (S, d_w) induced by the weighted points in S. The weighted distance function d_w on the set S of points is defined as follows: for any p, q in S, d_w(p, q) is equal to w(p) + d_pi(p, q) + w(q) if p e q, otherwise, d_w(p, q) is 0. Here, d_pi(p, q) is the Euclidean distance between p and q if points in S are in mathbb{R}^d, otherwise, it is the geodesic (Euclidean) distance between p and q. The following are our results: (1) When the weighted points in S are located in mathbb{R}^d, we compute a k-vertex fault-tolerant (4+epsilon)-spanner network of size O(k n). (2) When the weighted points in S are located in the relative interior of the free space of a polygonal domain cal P, we detail an algorithm to compute a k-vertex fault-tolerant (4+epsilon)-spanner network with O(frac{knsqrt{h+1}}{epsilon^2} lg{n}) edges. Here, h is the number of simple polygonal holes in cal P. (3) When the weighted points in S are located on a polyhedral terrain cal T, we propose an algorithm to compute a k-vertex fault-tolerant (4+epsilon)-spanner network, and the number of edges in this network is O(frac{kn}{epsilon^2} lg{n}).

Full work available at URL: https://arxiv.org/abs/2011.03354

Recommendations

• Fault-tolerant additive weighted geometric spanners
• Geometric Spanners for Weighted Point Sets
• Geometric spanners for weighted point sets
• Fault-tolerant geometric spanners
• scientific article; zbMATH DE number 1775403

zbMATH Keywords

computational geometryapproximation algorithmsgeometric spanners

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25)

Cites Work

• Geometric Spanner Networks
• There are planar graphs almost as good as the complete graph
• A Separator Theorem for Planar Graphs
• Planar spanners and approximate shortest path queries among obstacles in the plane
• On sparse spanners of weighted graphs
• Graph spanners
• Title not available (Why is that?)
• Classes of graphs which approximate the complete Euclidean graph
• Fast Greedy Algorithms for Constructing Sparse Geometric Spanners
• DELAUNAY AND DIAMOND TRIANGULATIONS CONTAIN SPANNERS OF BOUNDED DEGREE
• On bounded degree plane strong geometric spanners
• Constructing plane spanners of bounded degree and low weight
• Planar Separators
• Title not available (Why is that?)
• A Fast Algorithm for Constructing Sparse Euclidean Spanners
• Title not available (Why is that?)
• Region-fault tolerant geometric spanners
• Geometric spanners for weighted point sets
• Bypassing the embedding
• An optimal algorithm for computing angle-constrained spanners
• Computing the greedy spanner in near-quadratic time
• An Optimal Dynamic Spanner for Doubling Metric Spaces
• Kinetic spanners in \(\mathbb R^{d}\)
• Dynamic algorithms for geometric spanners of small diameter: Randomized solutions
• Title not available (Why is that?)
• Title not available (Why is that?)
• Efficient construction of a bounded-degree spanner with low weight
• Spanners of additively weighted point sets
• Stable roommates spanner
• Improved algorithms for constructing fault-tolerant spanners
• Sparse geometric graphs with small dilation
• New Doubling Spanners: Better and Simpler
• Fault-tolerant geometric spanners
• Minimum power assignment in wireless ad hoc networks with spanner property
• Geometric spanners with small chromatic number
• Spanners for geodesic graphs and visibility graphs
• Fault-tolerant additive weighted geometric spanners
• A simple and efficient kinetic spanner
• Small hop-diameter sparse spanners for doubling metrics
• On hierarchical routing in doubling metrics
• Truly Optimal Euclidean Spanners
• From hierarchical partitions to hierarchical covers: optimal fault-tolerant spanners for doubling metrics
• Geodesic spanners for points on a polyhedral terrain

Cited In (6)

• Vertex fault-tolerant spanners for weighted points in polygonal domains
• Title not available (Why is that?)
• Geometric spanners for weighted point sets
• Fault-tolerant geometric spanners
• Fault-tolerant additive weighted geometric spanners
• Geometric Spanners for Weighted Point Sets

This page was built for publication: Vertex Fault-Tolerant Geometric Spanners for Weighted Points

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6173263)