A Linear Time Euclidean Spanner on Imprecise Points
Jiemin Zeng, Jie Gao · 2014
An s-spanner on a set S of n points in Rd is a graph on S where for every two points p, q ∈ S, there exists a path between them in G whose length is less than or equal to s · |pq | where |pq | is the Euclidean distance between p and q. In this paper, we consider the construction of a Euclidean spanner for imprecise points where we take advantage of prior, inexact knowledge of our in-put. In particular, in the first phase, we preprocess n d-dimensional balls with radius r that are approximations of the input points with the guarantee that each input point lies within its respective ball. In the second phase, the specific points are revealed and we quickly compute a spanner using data from the preprocessing phase. We can compute (or update) the (1 + ε)-spanner in time O(n(r+ 1ε) d log(r+ 1ε)) after O(n(r+