External-Memory Computational Geometry (Preliminary Version)

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. >

Authors

• Michael T. Goodrich
• Jyh-Jong Tsay
• Darren Erik Vengroff
• Jeffrey Scott Vitter

Keywords

• Computational geometry
• Computer science
• Object oriented modeling
• Object oriented databases
• Large-scale systems
• Spatial databases
• Disk drives
• Design engineering
• Algorithm design and analysis
• Cost function
• Internal Computations
• Data Structure
• Optimization Algorithm
• Number Of Objects
• Convex Hull
• Large-scale Problems
• Divide-and-conquer
• Recursive Algorithm
• Delaunay Triangulation
• Points In Plane
• External Memory
• Divide-and-conquer Approach
• Vertical Segments
• Balanced Tree
• Disk Drive
• Block Units
• Geometric Problem
• N Log N
• Range Query
• Recursive Step
• Voronoi Diagram
• Linear Time
• Vertical Stripes
• Main Tree
• Internal Memory
• Input Point
• Binary Tree
• Tree Search