{"id":"arxiv/2607.25040","url":"https://arxiv.org/abs/2607.25040","tags":["cs.CG","math.CO"],"score":0,"title":"Geometric $(1+\\varepsilon)$-Spanners with Few Crossings","domain":"cs.CG","source":"arxiv","authors":["Kelvin Luu","Csaba D. Tóth"],"reviews":0,"subject":"cs.CG","summary":"For $n$ points in the plane and $\\varepsilon>0$, we construct a $(1+\\varepsilon)$-spanner with $O(n/\\varepsilon)$ edges in which every edge has $\\tilde{O}(1/\\varepsilon^3)$ crossings, the total number of crossings is $\\tilde{O}(n/\\varepsilon^4)$, and the ratio between the lengths of any two crossing edges is $O(1/\\varepsilon^2)$. Our spanner construction substantially improves on the previous upper bound for the number of crossings in a $(1+\\varepsilon)$-spanner, and it is the first spanner construction that ensures $O(1)$ crossings per edge for any constant $\\varepsilon>0$. In contrast, we…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-07-27","reactions":{}}