论文标题
加权点的顶点耐故障几何跨度
Vertex Fault-Tolerant Geometric Spanners for Weighted Points
论文作者
论文摘要
给定n个点的一组s，重量函数w可以将非负重量与s中的每个点相关联，正整数k \ ge 1和一个实数ε> 0，我们提出了计算跨度网络g（s，e）的算法，用于计算速度空间（s，d_w）的距离。 s，d_w（p，q）等于w（p） +d_π（p，q） + w（q），如果p \ ne q，否则，d_w（p，q）为0。在这里，d_π（p，q）是p和q之间的欧几里得距离（p，q），q之间的euclidean距离是\ andbb {r}^d，eucean and qe eudean（euce）（euce），则是eudean（euce）（euce）。以下是我们的结果：（1）当s中的加权点位于\ mathbb {r}^d中时，我们计算一个k-vertex耐受耐受剂（4+ε） - 大小O（k n）的Spanner网络。 （2）当s中的加权点位于多边形域\ cal p的自由空间的相对内部时，我们详细详细介绍了一种算法来计算具有O（\ frac {kn \ sqrt {kn \ sqrt {h+1}}}}^} {^2} {^2}的k-vertex耐受性（4+ε）-Spanner网络。在这里，H是\ Cal P中的简单多边形孔的数量（3）当S中的加权点位于多面体地形\ Cal T上时，我们提出了一种算法来计算一个k-vertex butteranterant（4+ε） - Spanner网络，并且该网络中的Edges数量是O（ \ lg {n}）。
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 ε> 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_π(p, q) + w(q) if p \ne q, otherwise, d_w(p, q) is 0. Here, d_π(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+ε)-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+ε)-spanner network with O(\frac{kn\sqrt{h+1}}{ε^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+ε)-spanner network, and the number of edges in this network is O(\frac{kn}{ε^2} \lg{n}).
