# Timothy M. Chan's Publications: Geometric shortest paths

### More algorithms for all-pairs shortest paths in weighted graphs

In the first part of the paper, we reexamine the all-pairs shortest paths (APSP) problem and present a new algorithm with running time approaching O(n^3 log^3log n / log^2 n), which improves all known algorithms for general real-weighted dense graphs.

In the second part of the paper, we use fast matrix multiplication to obtain truly subcubic APSP algorithms for a large class of "geometrically weighted" graphs, where the weight of an edge is a function of the coordinates of its vertices. For example, for graphs embedded in Euclidean space of a constant dimension d, we obtain a time bound near O(n^{3-(3-w)/(2d+4)}), where w < 2.376; in two dimensions, this is O(n^{2.922}). Our framework greatly extends the previously considered case of small-integer-weighted graphs, and incidentally also yields the first truly subcubic result (near O(n^{3-(3-w)/4}) = O(n^{2.844}) time) for APSP in real-vertex-weighted graphs, as well as an improved result (near O(n^{(3+w)/2}) = O(n^{2.688}) time) for the all-pairs lightest shortest path problem for small-integer-weighted graphs.

### Fly cheaply: on the minimum fuel consumption problem

(with
Alon Efrat)

In planning a flight, stops at intermediate airports are sometimes necessary to minimize fuel consumption, even if a direct flight is available. We investigate the problem of finding the cheapest path from one airport to another, given a set of n airports in R^2 and a function l: R^2 x R^2 -> R^+ representing the cost of a direct flight between any pair.

Given a source airport s, the cheapest-path map is a subdivision of R^2 where two points lie in the same region iff their cheapest paths from s use the same sequence of intermediate airports. We show a quadratic lower bound on the combinatorial complexity of this map for a class of cost functions. Nevertheless, we are able to obtain subquadratic algorithms to find the cheapest path from s to all other airports for any well-behaved cost function l: our general algorithm runs in O(n^{4/3+eps}) time, and a simpler, more practical variant runs in O(n^{3/2+eps}) time, while a special class of cost functions requires just O(n log n) time.