Secondary Memory Algorithms for Networks and Geometry

Kurt Mehlhorn (mehlhorn@mpi-sb.mpg.de)
Max Planck Institute für Informatik, Saarbrücken, Germany

Download slides here (gzipped PostScript file).

First an external memory model is presented. External memory consists of a finite number of disks added to the main memory. Data is moved in blocks between main and external memories.

The talk covers two works on external memory algorithms. The first one is a parallelization of Dijkstra's Algorithm for calculating shortest paths in a graph by Crauser, Mehlhorn, Neyer and Sauders. In this work Dijkstra's algorithm is modified by defining two criteria for the labeling of distances, called the in and out criteria. The algorithm runs in phases. The behavior of the algorithm is studied on random graphs. The expected number of phases is bounded theoretically and experimentally.

The second work is on Optimal External memory algorithms for some geometric problems by Crause, Ferragina, Mehlhorn, Neyer and Ramos. The problems considered are two and three dimensional convex hull, Voronoi diagrams, Delaunay triangulation and trapeziodal decomposition. The algorithm for trapeziodal decomposition is discussed in detail during the talk and are in the slides.

The library of efficient data structures and algorithms (LEDA) has been extended for implementation of secondary memory algorihms. This library, called LEDA-SM, includes data structures for external memory such as stacks, queues, priority queues, graphs, arrays and sorting algorithms.