The Traveling Salesman Problem (TSP) in the $d$-dimensional Euclidean space is among the oldest and most famous NP-hard optimization problems. In breakthrough works, Arora [J. ACM 1998] and Mitchell [SICOMP 1999] gave the first polynomial time approximation schemes. To improve the running time, Rao and Smith [STOC 1998] gave a randomized $(1/\varepsilon)^{O(1/\varepsilon^{d-1})}\cdot n\log n$ time approximation scheme. Bartal and Gottlieb [FOCS 2013] gave a randomized approximation scheme in $2^{(1/\varepsilon)^{O(d)}} n$ time, which is linear in $n$. Recently, Kisfaludi-Bak, Nederlof, and Węgrzycki [FOCS 2021] gave a randomized approximation scheme in $2^{O(1/\varepsilon^{d-1})} n \log n$ time, achieving a Gap-ETH tight dependence on $\varepsilon$. It is raised as a challenging open question by Kisfaludi-Bak, Nederlof, and Węgrzycki [FOCS 2021] whether a running time of $2^{O(1/\varepsilon^{d-1})}n$ is achievable. We answer their question positively by giving a randomized $2^{O(1/\varepsilon^{d-1})} n$ time approximation scheme for Euclidean TSP.

We consider Steiner spanners in Euclidean and non-Euclidean geometries. In the Euclidean setting, a recent line of work initiated by Le and Solomon [FOCS'19] and further improved by Chang et al. [SoCG'24] obtained Steiner $(1+\varepsilon)$-spanners of size $O_d(\varepsilon^{(1-d)/2}\log(1/\varepsilon)n)$, nearly matching the lower bounds of Bhore and Tóth [SIDMA'22]. We obtain Steiner $(1+\varepsilon)$-spanners of size $O_d(\varepsilon^{(1-d)/2}\log(1/\varepsilon)n)$ not only in $d$-dimensional Euclidean space, but also in $d$-dimensional spherical and hyperbolic space. For any fixed dimension $d$, the obtained edge count is optimal up to an $O(\log(1/\varepsilon))$ factor in each of these spaces. Unlike earlier constructions, our Steiner spanners are based on simple quadtrees, and they can be dynamically maintained, leading to efficient data structures for dynamic approximate nearest neighbours and bichromatic closest pair. In the hyperbolic setting, we also show that $2$-spanners in the hyperbolic plane must have $Ω(n\log n)$ edges, and we obtain a $2$-spanner of size $O_d(n\log n)$ in $d$-dimensional hyperbolic space, matching our lower bound for any constant $d$. Finally, we give a Steiner spanner with additive error $\varepsilon$ in hyperbolic space with $O_d(\varepsilon^{(1-d)/2}\log(α(n)/\varepsilon)n)$ edges, where $α(n)$ is the inverse Ackermann function. Our techniques generalize to closed orientable surfaces of constant curvature as well as to some quotient spaces.

In the (continuous) Euclidean k -center problem, given n points in ℝ d and an integer k , the goal is to find k center points in ℝ d that minimize the maximum Euclidean distance from any input point to its closest center. In this paper, we establish conditional lower bounds for this problem in constant dimensions in two settings. Parameterized by k : Assuming the Exponential Time Hypothesis (ETH), we show that there is no f ( k ) n o ( k 1−1/ d ) -time algorithm for the Euclidean k -center problem. This result shows that the algorithm of Agarwal and Procopiuc [SODA 1998; Algorithmica 2002] is essentially optimal. Furthermore, our lower bound rules out any (1+ε)-approximation algorithm running in time ( k /ε) o ( k 1−1/ d ) n O (1) , thereby establishing near-optimality of the corresponding approximation scheme by the same authors. Small k : Assuming the 3-SUM hypothesis, we prove that for any ε>0 there is no O ( n 2−ε )-time algorithm for the Euclidean 2-center problem in ℝ 3 . This settles an open question posed by Agarwal, Ben Avraham, and Sharir [SoCG 2010; Computational Geometry 2013]. In addition, under the same hypothesis, we prove that for any ε > 0, the Euclidean 6-center problem in ℝ 2 also admits no O ( n 2−ε )-time algorithm. The technical core of all our proofs is a novel geometric embedding of a system of linear equations. We construct a point set where each variable corresponds to a specific collection of points, and the geometric structure ensures that a small-radius clustering is possible if and only if the system has a valid solution.

We consider intersection graphs of disks of radius r in the hyperbolic plane. Unlike the Euclidean setting, these graph classes are different for different values of r, where very small r corresponds to an almost-Euclidean setting and r ∈ Ω(log n) corresponds to a firmly hyperbolic setting. We observe that larger values of r create simpler graph classes, at least in terms of separators and the computational complexity of the Independent Set problem. First, we show that intersection graphs of disks of radius r in the hyperbolic plane can be separated with 𝒪((1+1/r)log n) cliques in a balanced manner. Our second structural insight concerns Delaunay complexes in the hyperbolic plane and may be of independent interest. We show that for any set S of n points with pairwise distance at least 2r in the hyperbolic plane, the corresponding Delaunay complex has outerplanarity 1+𝒪((log n)/r), which implies a similar bound on the balanced separators and treewidth of such Delaunay complexes. Using this outerplanarity (and treewidth) bound we prove that Independent Set can be solved in n^𝒪(1+(log n)/r) time. The algorithm is based on dynamic programming on some unknown sphere cut decomposition that is based on the solution. The resulting algorithm is a far-reaching generalization of a result of Kisfaludi-Bak (SODA 2020), and it is tight under the Exponential Time Hypothesis. In particular, Independent Set is polynomial-time solvable in the firmly hyperbolic setting of r ∈ Ω(log n). Finally, in the case when the disks have ply (depth) at most 𝓁, we give a PTAS for Maximum Independent Set that has only quasi-polynomial dependence on 1/ε and 𝓁. Our PTAS is a further generalization of our exact algorithm.