Geometric (1+ε)-Spanners with Few Crossings
Abstract
For n points in the plane and ε>0, we construct a (1+ε)-spanner with O(n/ε) edges in which every edge has Õ(1/ε3) crossings, the total number of crossings is Õ(n/ε4), and 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.
Related
- Planarity and number of crossings in general models of random geometric graphs
- A linear bound for nested cycles without geometric crossings
- Almost Linear 3-Spanners of Temporal Cliques
- Asymptotic behavior of twisted Alexander invariants for hyperbolic knots with at most six crossings
- Morse Topology, Zero Products, and Elliptic Prime Crossings
BibTeX
@misc{luu2026geometric,
title = {{Geometric $(1+\varepsilon)$-Spanners with Few Crossings}},
author = {Kelvin Luu and Csaba D. Tóth},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2607.25040},
eprint = {2607.25040},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2607.25040},
}
RIS
TY - UNPB
TI - Geometric (1+ε)-Spanners with Few Crossings
AU - Kelvin Luu
AU - Csaba D. Tóth
PY - 2026
DA - 2026/10/17
PB - arXiv
DO - 10.48550/arxiv.2607.25040
UR - https://arxiv.org/abs/2607.25040
AB - For n points in the plane and ε>0, we construct a (1+ε)-spanner with O(n/ε) edges in which every edge has Õ(1/ε^3) crossings, the total number of crossings is Õ(n/ε^4), and 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.
ER -