License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SoCG.2021.15
URN: urn:nbn:de:0030-drops-138145
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/13814/
Go to the corresponding LIPIcs Volume Portal

Bhore, Sujoy ; Tóth, Csaba D.

Light Euclidean Steiner Spanners in the Plane

pdf-format:
LIPIcs-SoCG-2021-15.pdf (1 MB)

Abstract

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 a (1+ε)-spanner, and observed that additional Steiner points can substantially improve the lightness. Le and Solomon (2020) constructed Steiner (1+ε)-spanners of lightness O(ε^{-1}logΔ) 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.

BibTeX - Entry

@InProceedings{bhore_et_al:LIPIcs.SoCG.2021.15,
  author =	{Bhore, Sujoy and T\'{o}th, Csaba D.},
  title =	{{Light Euclidean Steiner Spanners in the Plane}},
  booktitle =	{37th International Symposium on Computational Geometry (SoCG 2021)},
  pages =	{15:1--15:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-184-9},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{189},
  editor =	{Buchin, Kevin and Colin de Verdi\`{e}re, \'{E}ric},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2021/13814},
  URN =		{urn:nbn:de:0030-drops-138145},
  doi =		{10.4230/LIPIcs.SoCG.2021.15},
  annote =	{Keywords: Geometric spanner, lightness, minimum weight}
}

Keywords: Geometric spanner, lightness, minimum weight
Collection: 37th International Symposium on Computational Geometry (SoCG 2021)
Issue Date: 2021
Date of publication: 02.06.2021

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI