Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userLight Euclidean Steiner Spanners in the Plane
76
0
0.0
(
0
)
Added by
Csaba D. Toth
Publication date
2020
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic 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 $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.
rate research
Read More
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+varepsilon)$-spanners with $O(n)$ edges and weight proportional to that of the Euclidean MST of $S$. Tight bounds on the dependence on $varepsilon>0$ for constant $din mathbb{N}$ have been established only recently. Le and Solomon (FOCS 2019) showed that Steiner points can substantially improve the lightness and sparsity of a $(1+varepsilon)$-spanner. They gave upper bounds of $tilde{O}(varepsilon^{-(d+1)/2})$ for the minimum lightness in dimensions $dgeq 3$, and $tilde{O}(varepsilon^{-(d-1))/2})$ for the minimum sparsity in $d$-space for all $dgeq 1$. They obtained lower bounds only in the plane ($d=2$). Le and Solomon (ESA 2020) also constructed Steiner $(1+varepsilon)$-spanners of lightness $O(varepsilon^{-1}logDelta)$ in the plane, where $Deltain Omega(sqrt{n})$ is the emph{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+varepsilon)$-spanners. Using a new geometric analysis, we establish lower bounds of $Omega(varepsilon^{-d/2})$ for the lightness and $Omega(varepsilon^{-(d-1)/2})$ for the sparsity of such spanners in Euclidean $d$-space for all $dgeq 2$. We use the geometric insight from our lower bound analysis to construct Steiner $(1+varepsilon)$-spanners of lightness $O(varepsilon^{-1}log n)$ for $n$ points in Euclidean plane.
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 objective of an online algorithm is to maintain a geometric $t$-spanner on $S_i={s_1,ldots, s_i}$ for each step~$i$. First, we establish a lower bound of $Omega(varepsilon^{-1}log n / log varepsilon^{-1})$ for the competitive ratio of any online $(1+varepsilon)$-spanner algorithm, for a sequence of $n$ points in 1-dimension. We show that this bound is tight, and there is an online algorithm that can maintain a $(1+varepsilon)$-spanner with competitive ratio $O(varepsilon^{-1}log n / log varepsilon^{-1})$. Next, we design online algorithms for sequences of points in $mathbb{R}^d$, for any constant $dge 2$, under the $L_2$ norm. We show that previously known incremental algorithms achieve a competitive ratio $O(varepsilon^{-(d+1)}log n)$. However, if the algorithm is allowed to use additional points (Steiner points), then it is possible to substantially improve the competitive ratio in terms of $varepsilon$. We describe an online Steiner $(1+varepsilon)$-spanner algorithm with competitive ratio $O(varepsilon^{(1-d)/2} log n)$. As a counterpart, we show that the dependence on $n$ cannot be eliminated in dimensions $d ge 2$. In particular, we prove that any online spanner algorithm for a sequence of $n$ points in $mathbb{R}^d$ under the $L_2$ norm has competitive ratio $Omega(f(n))$, where $lim_{nrightarrow infty}f(n)=infty$. Finally, we provide improved lower bounds under the $L_1$ norm: $Omega(varepsilon^{-2}/log varepsilon^{-1})$ in the plane and $Omega(varepsilon^{-d})$ in $mathbb{R}^d$ for $dgeq 3$.
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 techniques. Our results include the following: For the pairwise spanner problem, in which the pairs of vertices to be spanned arrive online, we present an efficient randomized $tilde{O}(n^{4/5})$-competitive algorithm for graphs with general lengths, where $n$ is the number of vertices. With uniform lengths, we give an efficient randomized $tilde{O}(n^{2/3+epsilon})$-competitive algorithm, and an efficient deterministic $tilde{O}(k^{1/2+epsilon})$-competitive algorithm, where $k$ is the number of terminal pairs. These are the first online algorithms for directed spanners. In the offline setting, the current best approximation ratio with uniform lengths is $tilde{O}(n^{3/5 + epsilon})$, due to Chlamtac, Dinitz, Kortsarz, and Laekhanukit (TALG 2020). For the directed Steiner forest problem with uniform costs, in which the pairs of vertices to be connected arrive online, we present an efficient randomized $tilde{O}(n^{2/3 + epsilon})$-competitive algorithm. The state-of-the-art online algorithm for general costs is due to Chakrabarty, Ene, Krishnaswamy, and Panigrahi (SICOMP 2018) and is $tilde{O}(k^{1/2 + epsilon})$-competitive. In the offline version, the current best approximation ratio with uniform costs is $tilde{O}(n^{26/45 + epsilon})$, due to Abboud and Bodwin (SODA 2018). A small modification of the online covering framework by Buchbinder and Naor implies a polynomial-time primal-dual approach with separation oracles, which a priori might perform exponentially many calls. We convert the online spanner problem and the online Steiner forest problem into online covering problems and round in a problem-specific fashion.
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 called a bottleneck Steiner tree. In this paper, we study the Euclidean bottleneck Steiner tree problem: given two sets, $P$ and $S$, and a positive integer $k le m$, find a bottleneck Steiner tree of $P$ with at most $k$ Steiner points. The problem has application in the design of wireless communication networks. We first show that the problem is NP-hard and cannot be approximated within factor $sqrt{2}$, unless $P=NP$. Then, we present a polynomial-time approximation algorithm with performance ratio 2.
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 Suri [SIAM J. Comput. 1999] gave an algorithm of $O(nlog n)$ time and $O(nlog n)$ space, where $n$ is the total number of vertices of all obstacles. Recently, by modifying Hershberger and Suris algorithm, Wang [SODA 2021] reduced the space to $O(n)$ while the runtime of the algorithm is still $O(nlog n)$. In this paper, we present a new algorithm of $O(n+hlog h)$ time and $O(n)$ space, provided that a triangulation of the free space is given, where $h$ is the number of obstacles. The algorithm, which improves the previous work when $h=o(n)$, is optimal in both time and space as $Omega(n+hlog h)$ is a lower bound on the runtime. Our algorithm builds a shortest path map for a source point $s$, so that given any query point $t$, the shortest path length from $s$ to $t$ can be computed in $O(log n)$ time and a shortest $s$-$t$ path can be produced in additional time linear in the number of edges of the path.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
