Geometric $(1+\epsilon )$-Spanners with Few Crossings

Kelvin Luu, Csaba D. Tóth

For $n$ points in the plane and $\epsilon >0$, we construct a $(1+\epsilon )$-spanner with $O(n/\epsilon )$ edges in which every edge has $\tilde{O}(1/{\epsilon }^3)$ crossin…