Dimitrios
Skrepetos,
PhD
candidate
David
R.
Cheriton
School
of
Computer
Science
This thesis studies shortest paths in geometric intersection graphs, which can model, among others, ad-hoc communication and transportation networks. First, we consider two classical problems in the field of algorithms, namely, Single-Source Shortest Paths (SSSP) and All-Pairs Shortest Paths (APSP): given a graph, we want to compute the shortest paths from one vertex to all other vertices (for the former) or the shortest path between every pair of vertices (for the latter).
Although there is a vast literature for these problems in many graph classes, the case of geometric intersection graphs has been only partially addressed.
In unweighted unit-disk graphs, we show that, after presorting the disk centers with respect to their coordinates, we can solve SSSP in linear time. Furthermore, we give the first (slightly) subquadratic-time APSP algorithm by using our new SSSP result, bit tricks, and a shifted-grid-based decomposition technique.
In unweighted, undirected geometric intersection graphs, we present a simple general technique that reduces APSP to static, offline intersection detection. Consequently, we give fast APSP algorithms for intersection graphs of arbitrary disks, axis-aligned line segments, arbitrary line segments, d-dimensional axis-aligned boxes, and d-dimensional axis-aligned unit hypercubes. We also provide a near-linear-time SSSP algorithm for intersection graphs of axis-aligned line segments, by a reduction to dynamic orthogonal point location.
Then we consider two problems that have received considerable attention lately. The first is that of computing the diameter of a graph, i.e., the longest shortest-path distance between any two vertices. In the second, we want to preprocess a graph into a data structure, called distance oracle, such that the shortest path (or its length) between any two query vertices can be found quickly. Since these problems are often too costly to solve exactly, we study their approximate versions.
Following a long line of research, we employ Voronoi diagrams to compute a (1/epsilon)-approximation of the diameter of an undirected, non-negatively-weighted planar graph in time near-linear on the input and polynomial on 1/epsilon (the previously best solution had exponential dependency on the latter). Using similar techniques, we can also construct the first (1+epsilon)-approximate distance oracles with similar preprocessing time and space and only O(log(1/epsilon)) query time.
In weighted unit-disk graphs, we present the first near-linear-time (1+epsilon)-approximation algorithm for the diameter (and for other related problems, such as the radius and the bichromatic closest pair), by combining techniques from computational geometry (well-separated pair decompositions) and planar graphs (shortest-path separators). We also show how to extend our approach to obtain O(1)-query-time (1+epsilon)-approximate distance oracles with near-linear preprocessing time and space, and then apply these, along with additional ideas, to build, in truly subcubic time, a data structure for the (1+epsilon)-approximate All-Pairs Bounded-Leg Shortest Paths (apBLSP) problem.