Spanners de Steiner Euclidianos Não Cruzantes de Sparseza Quase Ótima

Um spanner de Steiner Euclidiano não cruzante (1+ε) para um conjunto de pontos P ⊂ ℝ² é um grafo plano de linhas retas que, para quaisquer dois pontos a, b ∈ P, contém um caminho cuja extensão é no máximo 1+ε vezes a distância euclidiana entre a e b. Nós construímos um spanner de Steiner Euclidiano não cruzante (1+ε) com O(n/ε^{3/2}) arestas para qualquer conjunto de n pontos no plano. Este resultado melhora o anterior melhor limite superior de O(n/ε⁴) obtido há quase três décadas. Também estabelecemos um limite inferior quase correspondente: Existem n pontos no plano para os quais qualquer spanner de Steiner Euclidiano não cruzante (1+ε) possui Ω_μ(n/ε^{3/2-μ}) arestas para qualquer μ > 0. Nosso limite inferior utiliza generalizações recentes do teorema de Szemerédi-Trotter para incidências de disco-tubo na teoria da medida geométrica.