Externalmemory computational geometry (preliminary version

In this paper, we give new techniques for designing ecient algorithms for computational geometry prob-lems that are too large to be solved in internal memory, and 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.