Light Euclidean Steiner Spanners in the Plane
share
Lightness is a fundamental parameter for Euclidean spanners; it is the ratio of the spanner weight to the weight of the minimum spanning tree of a finite set of points in ℝ^d. In a recent breakthrough, Le and Solomon (2019) established the precise dependencies on ε>0 and d∈ℕ of the minimum lightness of (1+ε)-spanners, and observed that additional Steiner points can substantially improve the lightness. Le and Solomon (2020) constructed Steiner (1+ε)-spanners of lightness O(ε^-1logΔ) in the plane, where Δ≥Ω(√(n)) is the spread of the point set, defined as the ratio between the maximum and minimum distance between a pair of points. They also constructed spanners of lightness Õ(ε^-(d+1)/2) in dimensions d≥ 3. Recently, Bhore and Tóth (2020) established a lower bound of Ω(ε^-d/2) for the lightness of Steiner (1+ε)-spanners in ℝ^d, for d≥ 2. The central open problem in this area is to close the gap between the lower and upper bounds in all dimensions d≥ 2. In this work, we show that for every finite set of points in the plane and every ε>0, there exists a Euclidean Steiner (1+ε)-spanner of lightness O(ε^-1); this matches the lower bound for d=2. We generalize the notion of shallow light trees, which may be of independent interest, and use directional spanners and a modified window partitioning scheme to achieve a tight weight analysis.
READ FULL TEXT