The Complexity of Geodesic Spanners using Steiner Points

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 in the spanner 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 total spanner complexity is a recently-introduced measure of how compact a spanner is. 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 (mn^1/ (t+1) /k^1/ (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 and of complexity O (mn^1/t/k^1/t + n (n/k) ), for any integer t 1. We generalize this result to forests, and apply it to obtain a 22t-spanner in a simple polygon or a 6t-spanner in a polygonal domain, with total complexity O (mn^1/t (k) ^1+1/t/k^1/t + n² n).