Euclidean Noncrossing Steiner Spanners of Nearly Optimal Sparsity

Abstract

A Euclidean noncrossing Steiner $(1+\epsilon )$-spanner for a point set $P\subset {\mathbb{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 three decades ago. We also establish an almost matching lower bound: There exist $n$ points in the plane for which any Euclidean noncrossing Steiner $(1+\epsilon )$-spanner has ${\Omega }_{\mu }(n/{\epsilon }^{3/2-\mu })$ edges for any $\mu >0$. Our lower bound uses recent generalizations of the Szemerédi-Trotter theorem to disk-tube incidences in geometric measure theory.