Fast Thick-Thin Decomposition for Sparse Spanners on Hyperbolic Surfaces

Abstract

We consider spanners for point sets lying in the hyperbolic plane or on a closed hyperbolic surface with the restriction that spanner edges are not allowed to cross. This is a natural generalization of non-crossing Euclidean spanners. Thus, the resulting spanner graphs are embedded in the hyperbolic plane or on the hyperbolic surface. As our main contribution, we show that there are sparse $(1+\epsilon )$-spanners for these problems when we are allowed to use Steiner points: - on the hyperbolic plane we get a non-crossing Steiner $(1+\epsilon )$-spanner with $\mathcal{O}(n/{\epsilon }^2)$ edges, - on hyperbolic surfaces of genus $g$ we get a Steiner $(1+\epsilon )$-spanner with $\mathcal{O}(n/{\epsilon }^{3/2}+g/{\epsilon }^2)$ non-crossing edges, or with $\mathcal{O}(n/\sqrt{\epsilon }+g/\epsilon )$ edges that are allowed to cross. In particular, our spanners on surfaces have sparsity with linear dependence on $g$, rather than the easier-to-attain exponential dependence, and the terms $n/{\epsilon }^{3/2}$ and $n/\sqrt{\epsilon }$ match the current best Euclidean results for plane and crossing Steiner spanners, respectively. As a corollary of our non-crossing spanner and techniques from the existing literature on light spanners and minor-free TSP, we get an EPTAS for TSP on hyperbolic surfaces. Our surface constructions rely on the thick-thin decomposition, a standard tool for studying hyperbolic surfaces. For convex hyperbolic polygons, we introduce an analogous neck decomposition. We give algorithms that compute the thick-thin decomposition of a genus-$g$ surface in $\mathcal{O}(g^4\log g)$ time and the neck decomposition of an $n$-vertex polygon in $\mathcal{O}(n)$ time.