License: Creative Commons Attribution 4.0 license (CC BY 4.0)
when quoting this document, please refer to the following
DOI:
URN: urn:nbn:de:0030-drops-136586
URL:

;

### On Euclidean Steiner (1+ε)-Spanners

 pdf-format:

### Abstract

Lightness and sparsity are two natural parameters for Euclidean (1+ε)-spanners. Classical results show that, when the dimension d ∈ ℕ and ε > 0 are constant, every set S of n points in d-space admits an (1+ε)-spanners with O(n) edges and weight proportional to that of the Euclidean MST of S. Tight bounds on the dependence on ε > 0 for constant d ∈ ℕ have been established only recently. Le and Solomon (FOCS 2019) showed that Steiner points can substantially improve the lightness and sparsity of a (1+ε)-spanner. They gave upper bounds of Õ(ε^{-(d+1)/2}) for the minimum lightness in dimensions d ≥ 3, and Õ(ε^{-(d-1))/2}) for the minimum sparsity in d-space for all d ≥ 1. They obtained lower bounds only in the plane (d = 2). Le and Solomon (ESA 2020) also constructed Steiner (1+ε)-spanners of lightness O(ε^{-1}logΔ) in the plane, where Δ ∈ Ω(log n) is the spread of S, defined as the ratio between the maximum and minimum distance between a pair of points.
In this work, we improve several bounds on the lightness and sparsity of Euclidean Steiner (1+ε)-spanners. Using a new geometric analysis, we establish lower bounds of Ω(ε^{-d/2}) for the lightness and Ω(ε^{-(d-1)/2}) for the sparsity of such spanners in Euclidean d-space for all d ≥ 2. We use the geometric insight from our lower bound analysis to construct Steiner (1+ε)-spanners of lightness O(ε^{-1}log n) for n points in Euclidean plane.

### BibTeX - Entry

@InProceedings{bhore_et_al:LIPIcs.STACS.2021.13,
author =	{Bhore, Sujoy and T\'{o}th, Csaba D.},
title =	{{On Euclidean Steiner (1+\epsilon)-Spanners}},
booktitle =	{38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)},
pages =	{13:1--13:16},
series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN =	{978-3-95977-180-1},
ISSN =	{1868-8969},
year =	{2021},
volume =	{187},
editor =	{Bl\"{a}ser, Markus and Monmege, Benjamin},
publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address =	{Dagstuhl, Germany},
URL =		{https://drops.dagstuhl.de/opus/volltexte/2021/13658},
URN =		{urn:nbn:de:0030-drops-136586},
doi =		{10.4230/LIPIcs.STACS.2021.13},
annote =	{Keywords: Geometric spanner, (1+\epsilon)-spanner, lightness, sparsity, minimum weight}
}

 Keywords: Geometric spanner, (1+ε)-spanner, lightness, sparsity, minimum weight Seminar: 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021) Issue date: 2021 Date of publication: 10.03.2021

DROPS-Home | Fulltext Search | Imprint | Privacy