Euclidean Noncrossing Steiner Spanners of Nearly Optimal Sparsity
arXiv:2602.17801v1 Announce Type: new Abstract: A Euclidean noncrossing Steiner $(1+epsilon)$-spanner for a point set $Psubsetmathbb{R}^2$ is a planar straight-line graph that, for any two points $a, b in P$, contains a path whose length is at most $1+epsilon$ times the Euclidean distance between $a$ and $b$. We construct a Euclidean noncrossing Steiner $(1+epsilon)$-spanner with $O(n/epsilon^{3/2})$ edges for any set of $n$ points in the plane. This result improves upon the previous best upper bound of $O(n/epsilon^{4})$ obtained nearly […]