Tech Report CS-95-27

Dynamic and I/O-Efficient Algorithms for Computational Geometry and Graph Problems: Theoretical and Experimental Results

Yi-Jen Chiang

August 1995

Abstract:

As most important applications today are large-scale in nature, high-performance methods are becoming indispensable. Two promising computational paradigms for large-scale applications are dynamic and I/O-efficient computations. We give efficient dynamic data structures for several fundamental problems in computational geometry, including point location, ray shooting, shortest path, and minimum-link path. We also develop a collection of new techniques for designing and analyzing I/O-efficient algorithms for graph problems, and illustrate how these techniques can be applied to a wide variety of specific problems, including list ranking, Euler tour, expression-tree evaluation, least-common ancestors, connected and biconnected components, minimum spanning forest, ear decomposition, topological sorting, reachability, graph drawing, and visibility representation. Finally, we present an extensive experimental study comparing the practical I/O efficiency of four algorithms for the orthogonal segment intersection problem with large-scale test data. The experiments provide detailed quantitative evaluation of the performance of the four algorithms, and the observed behavior of the algorithms is consistent with their theoretical properties.

(complete text in pdf or gzipped postscript)