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 thesis: compressed postscript (.ps.gz) file and compressed .pdf (.pdf.gz) file
Back to Yi-Jen Chiang's home page