Euclidean Noncrossing Steiner Spanners of Nearly Optimal Sparsity
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2026
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866911458893234176 |
|---|---|
| author | Bhore, Sujoy Kisfaludi-Bak, Sándor Milenković, Lazar Tóth, Csaba D. Węgrzycki, Karol Wong, Sampson |
| author_facet | Bhore, Sujoy Kisfaludi-Bak, Sándor Milenković, Lazar Tóth, Csaba D. Węgrzycki, Karol Wong, Sampson |
| contents | A Euclidean noncrossing Steiner $(1+ε)$-spanner for a point set $P\subset\mathbb{R}^2$ is a planar straight-line graph that, for any two points $a, b \in 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/ε^{4})$ 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2602_17801 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | 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 Computational Geometry A Euclidean noncrossing Steiner $(1+ε)$-spanner for a point set $P\subset\mathbb{R}^2$ is a planar straight-line graph that, for any two points $a, b \in 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/ε^{4})$ 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. |
| title | Euclidean Noncrossing Steiner Spanners of Nearly Optimal Sparsity |
| topic | Computational Geometry |
| url | https://arxiv.org/abs/2602.17801 |