Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userTowards a Unified Theory of Light Spanners I: Fast (Yet Optimal) Constructions
160
0
0.0
(
0
)
Added by
Hung Le
Publication date
2021
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
Seminal works on light spanners over the years provide spanners with optimal or near-optimal lightness in various graph classes, such as in general graphs, Euclidean spanners, and minor-free graphs. Two shortcomings of all previous work on light spanners are: (1) The techniques are ad hoc per graph class, and thus cant be applied broadly (e.g., some require large stretch and are thus suitable to general graphs, while others are naturally suitable to stretch $1 + epsilon$). (2) The runtimes of these constructions are almost always sub-optimal, and usually far from optimal. This work aims at initiating a unified theory of light spanners by presenting a single framework that can be used to construct light spanners in a variety of graph classes. This theory is developed in two papers. The current paper is the first of the two -- it lays the foundations of the theory of light spanners and then applies it to design fast constructions with optimal lightness for several graph classes. Our new constructions are significantly faster than the state-of-the-art for every examined graph class; moreover, our runtimes are near-linear and usually optimal. Specifically, this paper includes the following results: (i) An $O(m alpha(m,n))$-time construction of $(2k-1)(1+epsilon)$-spanner with lightness $O(n^{1/k})$ for general graphs; (ii) An $O(nlog n)$-time construction of Euclidean $(1+epsilon)$-spanners with lightness and degree both bounded by constants in the basic algebraic computation tree (ACT) model. This construction resolves a major problem in the area of geometric spanners, which was open for three decades; (iii) An $O(nlog n)$-time construction of $(1+epsilon)$-spanners with constant lightness and degree, in the ACT model for unit disk graphs; (iv) a linear-time algorithm for constructing $(1+epsilon)$-spanners with constant lightness for minor-free graphs.
rate research
Read More
Resolving an open question from 2006, we prove the existence of light-weight bounded-degree spanners for unit ball graphs in the metrics of bounded doubling dimension, and we design a simple $mathcal{O}(log^*n)$-round distributed algorithm that given a unit ball graph $G$ with $n$ vertices and a positive constant $epsilon < 1$ finds a $(1+epsilon)$-spanner with constant bounds on its maximum degree and its lightness using only 2-hop neighborhood information. This immediately improves the algorithm of Damian, Pandit, and Pemmaraju which runs in $mathcal{O}(log^*n)$ rounds but has a $mathcal{O}(log Delta)$ bound on its lightness, where $Delta$ is the ratio of the length of the longest edge in $G$ to the length of the shortest edge. We further study the problem in the two dimensional Euclidean plane and we provide a construction with similar properties that has a constant average number of edge intersection per node. This is the first distributed low-intersection topology control algorithm to the best of our knowledge. Our distributed algorithms rely on the maximal independent set algorithm of Schneider and Wattenhofer that runs in $mathcal{O}(log^*n)$ rounds of communication. If a maximal independent set is known beforehand, our algorithms run in constant number of rounds.
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$.
For any constants $dge 1$, $epsilon >0$, $t>1$, and any $n$-point set $Psubsetmathbb{R}^d$, we show that there is a geometric graph $G=(P,E)$ having $O(nlog^2 nloglog n)$ edges with the following property: For any $Fsubseteq P$, there exists $F^+supseteq F$, $|F^+| le (1+epsilon)|F|$ such that, for any pair $p,qin Psetminus F^+$, the graph $G-F$ contains a path from $p$ to $q$ whose (Euclidean) length is at most $t$ times the Euclidean distance between $p$ and $q$. In the terminology of robust spanners (Bose et al, SICOMP, 42(4):1720--1736, 2013) the graph $G$ is a $(1+epsilon)k$-robust $t$-spanner of $P$. This construction is sparser than the recent constructions of Buchin, Ol`ah, and Har-Peled (arXiv:1811.06898) who prove the existence of $(1+epsilon)k$-robust $t$-spanners with $nlog^{O(d)} n$ edges.
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.
In this article, we provide new structural results and algorithms for the Homotopy Height problem. In broad terms, this problem quantifies how much a curve on a surface needs to be stretched to sweep continuously between two positions. More precisely, given two homotopic curves $gamma_1$ and $gamma_2$ on a combinatorial (say, triangulated) surface, we investigate the problem of computing a homotopy between $gamma_1$ and $gamma_2$ where the length of the longest intermediate curve is minimized. Such optimal homotopies are relevant for a wide range of purposes, from very theoretical questions in quantitative homotopy theory to more practical applications such as similarity measures on meshes and graph searching problems. We prove that Homotopy Height is in the complexity class NP, and the corresponding exponential algorithm is the best one known for this problem. This result builds on a structural theorem on monotonicity of optimal homotopies, which is proved in a companion paper. Then we show that this problem encompasses the Homotopic Frechet distance problem which we therefore also establish to be in NP, answering a question which has previously been considered in several different settings. We also provide an O(log n)-approximation algorithm for Homotopy Height on surfaces by adapting an earlier algorithm of Har-Peled, Nayyeri, Salvatipour and Sidiropoulos in the planar setting.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
