ﻻ يوجد ملخص باللغة العربية
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 $mathbb{R}^d$. In a recent breakthrough, Le and Solomon (2019) established the precise dependencies on $varepsilon>0$ and $din mathbb{N}$ of the minimum lightness of $(1+varepsilon)$-spanners, and observed that additional Steiner points can substantially improve the lightness. Le and Solomon (2020) constructed Steiner $(1+varepsilon)$-spanners of lightness $O(varepsilon^{-1}logDelta)$ in the plane, where $Deltageq Omega(sqrt{n})$ is the emph{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 $tilde{O}(varepsilon^{-(d+1)/2})$ in dimensions $dgeq 3$. Recently, Bhore and T{o}th (2020) established a lower bound of $Omega(varepsilon^{-d/2})$ for the lightness of Steiner $(1+varepsilon)$-spanners in $mathbb{R}^d$, for $dge 2$. The central open problem in this area is to close the gap between the lower and upper bounds in all dimensions $dgeq 2$. In this work, we show that for every finite set of points in the plane and every $varepsilon>0$, there exists a Euclidean Steiner $(1+varepsilon)$-spanner of lightness $O(varepsilon^{-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.
Lightness and sparsity are two natural parameters for Euclidean $(1+varepsilon)$-spanners. Classical results show that, when the dimension $din mathbb{N}$ and $varepsilon>0$ are constant, every set $S$ of $n$ points in $d$-space admits an $(1+varepsi
In this paper, we study the online Euclidean spanners problem for points in $mathbb{R}^d$. Suppose we are given a sequence of $n$ points $(s_1,s_2,ldots, s_n)$ in $mathbb{R}^d$, where point $s_i$ is presented in step~$i$ for $i=1,ldots, n$. The objec
We present online algorithms for directed spanners and Steiner forests. These problems fall under the unifying framework of online covering linear programming formulations, developed by Buchbinder and Naor (MOR, 34, 2009), based on primal-dual techni
Given two sets of points in the plane, $P$ of $n$ terminals and $S$ of $m$ Steiner points, a Steiner tree of $P$ is a tree spanning all points of $P$ and some (or none or all) points of $S$. A Steiner tree with length of longest edge minimized is cal
Given a set of pairwise disjoint polygonal obstacles in the plane, finding an obstacle-avoiding Euclidean shortest path between two points is a classical problem in computational geometry and has been studied extensively. Previously, Hershberger and