2026/07/27 by Kelvin Luu, Csaba D. Tóth
#cs.CG #math.CO
For n points in the plane and an ε>0, we construct a (1+ε)-spanner with O(n/ε) edges in which every edge has O(1/ε3) crossings, hence the total number of crossings is O(n/ε4), furthermore the ratio between the lengths of any two crossing edges is O(1/ε2). Our spanner construction substantially improves on the previous upper bound for the number of crossings in a (1+ε)-spanner, and it is the first spanner construction that ensures O(1) crossings per edge for any constant ε>0. In contrast, we construct: n points in the plane for which every (1+ε)-spanner has Ω(n/ε3) crossings, n points for which every (1+ε)-spanner has an edge with Ω(1/ε5/2) crossings, and 4 points for which every (1+ε)-spanner contains two crossing edges where one is Ω(1/ε) times longer than the other.