2026-09-05T11:58:35Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:25821 2026-06-23T12:59:00Z ddc:004 open_access

Euclidean Noncrossing Steiner Spanners of Nearly Optimal Sparsity Bhore, Sujoy Kisfaludi‑Bak, Sándor Milenković, Lazar Tóth, Csaba D. Węgrzycki, Karol Wong, Sampson geometric network design spanners crossing number incidences A Euclidean noncrossing Steiner (1+ε)-spanner for a point set P ⊂ ℝ² is a planar straight-line graph that, for any two points a, b ∈ P, contains a path whose length is at most 1+ε times the Euclidean distance between a and b. We construct a Euclidean noncrossing Steiner (1+ε)-spanner with O(n/ε^{3/2}) edges for any set of n points in the plane. This result improves upon the previous best upper bound of O(n/ε⁴) 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+ε)-spanner has Ω_μ(n/ε^{3/2-μ}) edges for any μ > 0. Our lower bound uses recent generalizations of the Szemerédi-Trotter theorem to disk-tube incidences in geometric measure theory. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Sujoy Bhore and Sándor Kisfaludi‑Bak and Lazar Milenković and Csaba D. Tóth and Karol Węgrzycki and Sampson Wong 2026 Is Part Of LIPIcs, Volume 367, 42nd International Symposium on Computational Geometry (SoCG 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SoCG.2026.15 urn:nbn:de:0030-drops-258210 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2026.15 eng https://creativecommons.org/licenses/by/4.0/legalcode