A geometric \(t\)-spanner \(\mathcal{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 \(\mathcal{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 \(\Theta (m)\) segments and thus have non-constant complexity. The spanner complexity is a recently-introduced 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 \(\Omega(nm/k)\) lower bound on the worst-case complexity of any \((3-\eps)\)-spanner, and an \(\Omega(mn^{1/(t+1)}/k^{1/(t+1)})\) lower bound on the worst-case complexity of any \((t-\eps)\)-spanner, for any constant \(\eps \in (0,1)\) and integer constant \(t \geq 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(mn^{1/t}/k^{1/t} + n \log (n/k))\), for any integer \(t \geq 1\). We generalize this result to forests, and apply it to obtain a \(2\sqrt{2}t\)-spanner in a simple polygon with total complexity \(O(mn^{1/t}(\log k)^{1+1/t}/k^{1/t} + n\log^2 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+\varepsilon)\), for any constant \(\varepsilon \in (0,2k)\), and how to build a \(6t\)-spanner in a polygonal domain with the same complexity.