Loading...
External-Memory Computational Geometry
Goodrich, Michael T. Tsay, Jyh-Jong Vengroff, Darren Erik Vitter, Jeffrey Scott
Goodrich, Michael T.
Tsay, Jyh-Jong
Vengroff, Darren Erik
Vitter, Jeffrey Scott
Citations
Altmetric:
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.
Description
(c) 1993 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other users, including reprinting/ republishing this material for advertising or promotional purposes, creating new collective works for resale or redistribution to servers or lists, or reuse of any copyrighted components of this work in other works.
Date
1993
Journal Title
Journal ISSN
Volume Title
Publisher
IEEE
Files
Loading...
GTV93.ecg.pdf
Adobe PDF, 247.4 KB
Research Projects
Organizational Units
Journal Issue
Keywords
Citation
M. T. Goodrich, J.-J. Tsay, D. E. Vengroff, and J. S. Vitter. “External-Memory Computational Geometry,” Proceedings of the 34th Annual IEEE Symposium on Foundations of Computer Science (FOCS ’93), Palo Alto, CA, November 1993, 714–723. http://dx.doi.org/10.1109/SFCS.1993.366816