DIKU Bits: Providing directions using efficient algorithms

Speaker

Mikkel Thorup, Professor in the AC (Algorithms and Complexity) section.

Title

Providing directions using efficient algorithms

Abstract

We show how to preprocess a large road network (planar graph) so we can quickly provide directions to get from X to Y. If the network has n nodes, then the obvious solution is to provide a huge table of size n x n telling what to do for any pair of nodes, but our preprocessing results in a data structure that is only a bit larger than the input network, yet which can provide distances and directions in constant time.

The talk is algorithmic focusing on the simple mathematical ideas leading to this efficient representation.