Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userSublinear Average-Case Shortest Paths in Weighted Unit-Disk Graphs
87
0
0.0
(
0
)
Added by
Adam Karczmarz
Publication date
2021
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
We consider the problem of computing shortest paths in weighted unit-disk graphs in constant dimension $d$. Although the single-source and all-pairs variants of this problem are well-studied in the plane case, no non-trivial exact distance oracles for unit-disk graphs have been known to date, even for $d=2$. The classical result of Sedgewick and Vitter [Algorithmica 86] shows that for weighted unit-disk graphs in the plane the $A^*$ search has average-case performance superior to that of a standard shortest path algorithm, e.g., Dijkstras algorithm. Specifically, if the $n$ corresponding points of a weighted unit-disk graph $G$ are picked from a unit square uniformly at random, and the connectivity radius is $rin (0,1)$, $A^*$ finds a shortest path in $G$ in $O(n)$ expected time when $r=Omega(sqrt{log n/n})$, even though $G$ has $Theta((nr)^2)$ edges in expectation. In other words, the work done by the algorithm is in expectation proportional to the number of vertices and not the number of edges. In this paper, we break this natural barrier and show even stronger sublinear time results. We propose a new heuristic approach to computing point-to-point exact shortest paths in unit-disk graphs. We analyze the average-case behavior of our heuristic using the same random graph model as used by Sedgewick and Vitter and prove it superior to $A^*$. Specifically, we show that, if we are able to report the set of all $k$ points of $G$ from an arbitrary rectangular region of the plane in $O(k + t(n))$ time, then a shortest path between arbitrary two points of such a random graph on the plane can be found in $O(1/r^2 + t(n))$ expected time. In particular, the state-of-the-art range reporting data structures imply a sublinear expected bound for all $r=Omega(sqrt{log n/n})$ and $O(sqrt{n})$ expected bound for $r=Omega(n^{-1/4})$ after only near-linear preprocessing of the point set.
rate research
Read More
Given a set P of n points in the plane, a unit-disk graph G_{r}(P) with respect to a radius r is an undirected graph whose vertex set is P such that an edge connects two points p, q in P if the Euclidean distance between p and q is at most r. The length of any path in G_r(P) is the number of edges of the path. Given a value lambda>0 and two points s and t of P, we consider the following reverse shortest path problem: finding the smallest r such that the shortest path length between s and t in G_r(P) is at most lambda. It was known previously that the problem can be solved in O(n^{4/3} log^3 n) time. In this paper, we present an algorithm of O(lfloor lambda rfloor cdot n log n) time and another algorithm of O(n^{5/4} log^2 n) time.
In this paper we consider the decremental single-source shortest paths (SSSP) problem, where given a graph $G$ and a source node $s$ the goal is to maintain shortest distances between $s$ and all other nodes in $G$ under a sequence of online adversarial edge deletions. In their seminal work, Even and Shiloach [JACM 1981] presented an exact solution to the problem in unweighted graphs with only $O(mn)$ total update time over all edge deletions. Their classic algorithm was the state of the art for the decremental SSSP problem for three decades, even when approximate shortest paths are allowed. A series of results showed how to improve upon $O(mn)$ if approximation is allowed, culminating in a recent breakthrough of Henzinger, Krinninger and Nanongkai [FOCS 14], who presented a $(1+epsilon)$-approximate algorithm for undirected weighted graphs whose total update time is near linear: $O(m^{1+o(1)}log(W))$, where $W$ is the ratio of the heaviest to the lightest edge weight in the graph. In this paper they posed as a major open problem the question of derandomizing their result. Until very recently, all known improvements over the Even-Shiloach algorithm were randomized and required the assumption of a non-adaptive adversary. In STOC 2016, Bernstein and Chechik showed the first emph{deterministic} algorithm to go beyond $O(mn)$ total update time: the algorithm is also $(1+epsilon)$-approximate, and has total update time $tilde{O}(n^2)$. In SODA 2017, the same authors presented an algorithm with total update time $tilde{O}(mn^{3/4})$. However, both algorithms are restricted to undirected, unweighted graphs. We present the emph{first} deterministic algorithm for emph{weighted} undirected graphs to go beyond the $O(mn)$ bound. The total update time is $tilde{O}(n^2 log(W))$.
Let $Vsubsetmathbb{R}^2$ be a set of $n$ sites in the plane. The unit disk graph $DG(V)$ of $V$ is the graph with vertex set $V$ in which two sites $v$ and $w$ are adjacent if and only if their Euclidean distance is at most $1$. We develop a compact routing scheme for $DG(V)$. The routing scheme preprocesses $DG(V)$ by assigning a label $l(v)$ to every site $v$ in $V$. After that, for any two sites $s$ and $t$, the scheme must be able to route a packet from $s$ to $t$ as follows: given the label of a current vertex $r$ (initially, $r=s$) and the label of the target vertex $t$, the scheme determines a neighbor $r$ of $r$. Then, the packet is forwarded to $r$, and the process continues until the packet reaches its desired target $t$. The resulting path between the source $s$ and the target $t$ is called the routing path of $s$ and $t$. The stretch of the routing scheme is the maximum ratio of the total Euclidean length of the routing path and of the shortest path in $DG(V)$, between any two sites $s, t in V$. We show that for any given $varepsilon>0$, we can construct a routing scheme for $DG(V)$ with diameter $D$ that achieves stretch $1+varepsilon$ and label size $O(log Dlog^3n/loglog n)$ (the constant in the $O$-Notation depends on $varepsilon$). In the past, several routing schemes for unit disk graphs have been proposed. Our scheme is the first one to achieve poly-logarithmic label size and arbitrarily small stretch without storing any additional information in the packet.
We prove a geometric version of the graph separator theorem for the unit disk intersection graph: for any set of $n$ unit disks in the plane there exists a line $ell$ such that $ell$ intersects at most $O(sqrt{(m+n)log{n}})$ disks and each of the halfplanes determined by $ell$ contains at most $2n/3$ unit disks from the set, where $m$ is the number of intersecting pairs of disks. We also show that an axis-parallel line intersecting $O(sqrt{m+n})$ disks exists, but each halfplane may contain up to $4n/5$ disks. We give an almost tight lower bound (up to sublogarithmic factors) for our approach, and also show that no line-separator of sublinear size in $n$ exists when we look at disks of arbitrary radii, even when $m=0$. Proofs are constructive and suggest simple algorithms that run in linear time. Experimental evaluation has also been conducted, which shows that for random instances our method outperforms the method by Fox and Pach (whose separator has size $O(sqrt{m})$).
This paper presents an optimal $Theta(n log n)$ algorithm for determining time-minimal rectilinear paths among $n$ transient rectilinear obstacles. An obstacle is transient if it exists in the scene only for a specific time interval, i.e., it appears and then disappears at specific times. Given a point robot moving with bounded speed among transient rectilinear obstacles and a pair of points $s$, $d$, we determine a time-minimal, obstacle-avoiding path from $s$ to $d$. The main challenge in solving this problem arises as the robot may be required to wait for an obstacle to disappear, before it can continue moving toward the destination. Our algorithm builds on the continuous Dijkstra paradigm, which simulates propagating a wavefront from the source point. We also solve a query version of this problem. For this, we build a planar subdivision with respect to a fixed source point, so that minimum arrival time to any query point can be reported in $O(log n)$ time, using point location for the query point in this subdivision.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
