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.