External-memory computational geometry
- 30 December 2002
- proceedings article
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 714-723
- https://doi.org/10.1109/sfcs.1993.366816
Abstract
In this paper we give new techniques for designing efficient algorithms for computational geometry problems that are too large to be solved in internal memory. 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 first known optimal results but also of tremendous practical value. Our methods also produce the first known optimal algorithms 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.Keywords
This publication has 25 references indexed in Scilit:
- An efficient algorith for determining the convex hull of a finite planar setPublished by Elsevier ,2002
- Algorithms for parallel memory, II: Hierarchical multilevel memoriesAlgorithmica, 1994
- Algorithms for parallel memory, I: Two-level memoriesAlgorithmica, 1994
- Constructing the convex hull of a partially sorted set of pointsComputational Geometry, 1993
- Optimal Parallel Randomized Algorithms for Three-Dimensional Convex Hulls and Related ProblemsSIAM Journal on Computing, 1992
- Optimal cooperative search in fractional cascaded data structuresPublished by Association for Computing Machinery (ACM) ,1990
- Making data structures persistentJournal of Computer and System Sciences, 1989
- Primitives for the manipulation of general subdivisions and the computation of VoronoiACM Transactions on Graphics, 1985
- Computational GeometryPublished by Springer Nature ,1985
- The TWA reservation systemCommunications of the ACM, 1984