  We study spanners in planar domains, including polygonal domains, polyhedral
terrain, and planar metrics. Previous work showed that for any constant
$\epsilon\in (0,1)$, one could construct a $(2+\epsilon)$-spanner with
$O(n\log(n))$ edges (SICOMP 2019), and there is a lower bound of $\Omega(n^2)$
edges for any $(2-\epsilon)$-spanner (SoCG 2015). The main open question is
whether a linear number of edges suffices and the stretch can be reduced to
$2$. We resolve this problem by showing that for stretch $2$, one needs
$\Omega(n\log n)$ edges, and for stretch $2+\epsilon$ for any fixed $\epsilon
\in (0,1)$, $O(n)$ edges are sufficient. Our lower bound is the first
super-linear lower bound for stretch $2$.
  En route to achieve our result, we introduce the problem of constructing
non-Steiner tree covers for metrics, which is a natural variant of the
well-known Steiner point removal problem for trees (SODA 2001). Given a tree
and a set of terminals in the tree, our goal is to construct a collection of a
small number of dominating trees such that for every two points, at least one
tree in the collection preserves their distance within a small stretch factor.
Here, we identify an unexpected threshold phenomenon around $2$ where a sharp
transition from $n$ trees to $\Theta(\log n)$ trees and then to $O(1)$ trees
happens. Specifically, (i) for stretch $ 2-\epsilon$, one needs $\Omega(n)$
trees; (ii) for stretch $2$, $\Theta(\log n)$ tree is necessary and sufficient;
and (iii) for stretch $2+\epsilon$, a constant number of trees suffice.
Furthermore, our lower bound technique for the non-Steiner tree covers of
stretch $2$ has further applications in proving lower bounds for two related
constructions in tree metrics: reliable spanners and locality-sensitive
orderings. Our lower bound for locality-sensitive orderings matches the best
upper bound (STOC 2022).
