The Complexity of Geodesic Spanners Using Steiner Points

Abstract

A geometric t-spanner G on a set S of n point sites in a metric space P is a subgraph of the complete graph on S such that for every pair of sites p, q the distance in G is a most t times the distance d(p, q) in P. We call a connection between two sites a link. In some settings, such as when P is a simple polygon with m vertices and a link is a shortest path in P, links can consist of Θ(m) segments and thus have non-constant complexity. The spanner complexity is a measure of how compact a spanner is, which is equal to the sum of the complexities of all links in the spanner. In this paper, we study what happens if we are allowed to introduce k Steiner points to reduce the spanner complexity. We study such Steiner spanners in simple polygons, polygonal domains, and edge-weighted trees. Surprisingly, we show that Steiner points have only limited utility. For a spanner that uses k Steiner points, we provide an Ω(nm/k) lower bound on the worst-case complexity of any (3 − ε)spanner, and an Ω(mn1/(t+1)/k1/(t+1)) lower bound on the worst-case complexity of any (t − ε)spanner, for any constant ε ∈ (0, 1) and integer constant t ≥ 2. These lower bounds hold in all settings. Additionally, we show NP-hardness for the problem of deciding whether a set of sites in a polygonal domain admits a 3-spanner with a given maximum complexity using k Steiner points. On the positive side, for trees we show how to build a 2t-spanner that uses k Steiner points of complexity O(mn1/t/k1/t + nlog(n/k)), for any integer t ≥ 1. We generalize this result to forests, and apply it to obtain a 2√2t-spanner in a simple polygon with total complexity O(mn1/t(log k)1+1/t/k1/t + nlog2 n). When a link in the spanner can be any path between two sites, we show how to improve the spanning ratio in a simple polygon to (2k + ε), for any constant ε ∈ (0, 2k), and how to build a 6t-spanner in a polygonal domain with the same complexity.