External-Memory Computational Geometry

Abstract

In this paper we give new techniques for designing e cient algorithms for computational geometry prob- lems that are too large to be solved in internal mem- ory. We use these techniques to develop optimal and practical algorithms for a number of important large- scale problems. We discuss our algorithms primarily in the context of single processor/single disk machines, a domain in which they are not only the rst known optimal results but also of tremendous practical value. Our methods also produce the rst known optimal al- gorithms for a wide range of two-level and hierarchical multilevel memory models, including parallel models. The algorithms are optimal both in terms of I/O cost and internal computation.