The Complexity of Geodesic Spanners

A geometric $t$-spanner for a set $S$ of $n$ point sites is an edge-weighted graph for which the (weighted) distance between any two sites $p,q \in S$ is at most $t$ times the original distance between $p$ and $q$. We study geometric $t$-spanners for point sets in a constrained two-dimensional environment $P$. In such cases, the edges of the spanner may have non-constant complexity. Hence, we introduce a novel spanner property: the spanner complexity, that is, the total complexity of all edges in the spanner. Let $S$ be a set of $n$ point sites in a simple polygon $P$ with $m$ vertices. We present an algorithm to construct, for any constant $\varepsilon>0$ and fixed integer $k \geq 1$, a $(2k + \varepsilon)$-spanner with complexity $O(mn^{1/k} + n\log^2 n)$ in $O(n\log^2n + m\log n + K)$ time, where $K$ denotes the output complexity. When we consider sites in a polygonal domain $P$ with holes, we can construct such a $(2k+\varepsilon)$-spanner of similar complexity in $O(n^2 \log m + nm\log m + K)$ time. Additionally, for any constant $\varepsilon \in (0,1)$ and integer constant $t \geq 2$, we show a lower bound for the complexity of any $(t-\varepsilon)$-spanner of $\Omega(mn^{1/(t-1)} + n)$.