The Complexity of Geodesic Spanners
share
A geometric t-spanner for a set S of n point sites is an edge-weighted graph for which the (weighted) distance between any two sites p,q ∈ S is at most t times the original distance between p and q. We study geometric t-spanners for point sets in a constrained two-dimensional environment P. In such cases, the edges of the spanner may have non-constant complexity. Hence, we introduce a novel spanner property: the spanner complexity, that is, the total complexity of all edges in the spanner. Let S be a set of n point sites in a simple polygon P with m vertices. We present an algorithm to construct, for any constant ε>0 and fixed integer k ≥ 1, a (2k + ε)-spanner with complexity O(mn^1/k + nlog^2 n) in O(nlog^2n + mlog n + K) time, where K denotes the output complexity. When we consider sites in a polygonal domain P with holes, we can construct such a (2k+ε)-spanner of similar complexity in O(n^2 log m + nmlog m + K) time. Additionally, for any constant ε∈ (0,1) and integer constant t ≥ 2, we show a lower bound for the complexity of any (t-ε)-spanner of Ω(mn^1/(t-1) + n).
READ FULL TEXT