Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userGeneralized Sweeping Line Spanners
111
0
0.0
(
0
)
Added by
Andr\\'e van Renssen
Publication date
2021
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
We present sweeping line graphs, a generalization of $Theta$-graphs. We show that these graphs are spanners of the complete graph, as well as of the visibility graph when line segment constraints or polygonal obstacles are considered. Our proofs use general inductive arguments to make the step to the constrained setting that could apply to other spanner constructions in the unconstrained setting, removing the need to find separate proofs that they are spanning in the constrained and polygonal obstacle settings.
rate research
Read More
In this thesis, we study two different graph problems. The first problem revolves around geometric spanners. Here, we have a set of points in the plane and we want to connect them with straight line segments, such that there is a path between each pair of points that does not make a large detour. If we achieve this, the resulting graph is called a spanner. We focus our attention on $Theta$-graphs, which are constructed by connecting each point with its nearest neighbour in a fixed number of cones. Although this construction is very straight-forward, it has proven challenging to fully determine the properties of the resulting graphs. We show that if the construction uses 5 cones, the resulting graphs are still spanners. This was the only number of cones for which this question remained unanswered. We also present a routing strategy on the half-$Theta_6$-graph, a variant of the graph with 6 cones. We show that our routing strategy finds a path whose length is at most a constant factor from the straight-line distance between the endpoints. Moreover, we show that this routing strategy is optimal. In the second part, we turn our attention to flips in triangulations. A flip is a simple operation that transforms one triangulation into another. It turns out that with enough flips, we can transform any triangulation into any other. But how many flips is enough? We present an improved upper bound of $5.2n - 33.6$ on the maximum flip distance between any pair of triangulations with n vertices. Along the way, we prove matching lower bounds on each step in the current algorithm, including a tight bound of $(3n - 9)/5$ flips needed to make a triangulation 4-connected. In addition, we prove tight $Theta(n log n)$ bounds on the number of flips required in several settings where the edges have unique labels.
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$.
Let $P subset mathbb{R}^2$ be a planar $n$-point set such that each point $p in P$ has an associated radius $r_p > 0$. The transmission graph $G$ for $P$ is the directed graph with vertex set $P$ such that for any $p, q in P$, there is an edge from $p$ to $q$ if and only if $d(p, q) leq r_p$. Let $t > 1$ be a constant. A $t$-spanner for $G$ is a subgraph $H subseteq G$ with vertex set $P$ so that for any two vertices $p,q in P$, we have $d_H(p, q) leq t d_G(p, q)$, where $d_H$ and $d_G$ denote the shortest path distance in $H$ and $G$, respectively (with Euclidean edge lengths). We show how to compute a $t$-spanner for $G$ with $O(n)$ edges in $O(n (log n + log Psi))$ time, where $Psi$ is the ratio of the largest and smallest radius of a point in $P$. Using more advanced data structures, we obtain a construction that runs in $O(n log^5 n)$ time, independent of $Psi$. We give two applications for our spanners. First, we show how to use our spanner to find a BFS tree in $G$ from any given start vertex in $O(n log n)$ time (in addition to the time it takes to build the spanner). Second, we show how to use our spanner to extend a reachability oracle to answer geometric reachability queries. In a geometric reachability query we ask whether a vertex $p$ in $G$ can reach a target $q$ which is an arbitrary point in the plane (rather than restricted to be another vertex $q$ of $G$ in a standard reachability query). Our spanner allows the reachability oracle to answer geometric reachability queries with an additive overhead of $O(log nlog Psi)$ to the query time and $O(n log Psi)$ to the space.
Efficient algorithms are presented for constructing spanners in geometric intersection graphs. For a unit ball graph in R^k, a (1+epsilon)-spanner is obtained using efficient partitioning of the space into hypercubes and solving bichromatic closest pair problems. The spanner construction has almost equivalent complexity to the construction of Euclidean minimum spanning trees. The results are extended to arbitrary ball graphs with a sub-quadratic running time. For unit ball graphs, the spanners have a small separator decomposition which can be used to obtain efficient algorithms for approximating proximity problems like diameter and distance queries. The results on compressed quadtrees, geometric graph separators, and diameter approximation might be of independent interest.
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.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
