2017/06/20 by Abolfazl Poureidi, Mohammad Farshi, Poureidi, Abolfazl +1
Computer Science · #Computational Geometry (cs.CG) #FOS: Computer and information sciences #cs.CG
paper · pdf · doi:10.48550/arxiv.1706.06287
arxiv created 2017/06/20 · arxiv updated 2017/06/21
Given a real number t>1, a geometric t-spanner is a geometric graph for a point set in ℝd with straight lines between vertices such that the ratio of the shortest-path distance between every pair of vertices in the graph (with Euclidean edge lengths) to their actual Euclidean distance is at most t. An imprecise point set is modeled by a set R of regions in ℝd. If one chooses a point in each region of R, then the resulting point set is called a precise instance of~R. An imprecise t-spanner for an imprecise point set R is a graph G=(R,E) such that for each precise instance S of R, graph GS=(S,ES), where ES is the set of edges corresponding to E, is a t-spanner. In this paper, we show that, given a real number t>1, there is an imprecise point set R of n straight-line segments in the plane such that any imprecise t-spanner for R has Ω(n2) edges. Then, we propose an algorithm that computes a Well-Separated Pair Decomposition (WSPD) of size \cal O(n) for a set of n pairwise disjoint d-dimensional balls with arbitrary sizes. Given a real number t>1 and given a set of n pairwise disjoint d-balls with arbitrary sizes, we use this WSPD to compute in \cal O(nlog n+n/(t-1)d) time an imprecise t-spanner with \cal O(n/(t-1)d) edges for balls.