The Complexity of Geodesic Spanners using Steiner Points

Sarita de Berg, Tim Ophelders, Irene Parada +2

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 d…