|
External-Storage Data Structures for Plane-Sweep Algorithms
Lars Arge June 1994 |
Abstract:
In this paper we develop a technique for transforming an
internal memory datastructure into an external storage data structure
suitable for plane-sweep algorithms. We use this technique to develop
external storage versions of the range tree and the segment tree. We also
obtain an external priority queue. Using the first two structures, we solve
the orthogonal segment intersection, the isothetic rectangle intersection,
and the batched range searching problem in the optimal number of
I/O-operations. Unlike previously known I/O-algorithms the developed
algorithms are straightforward generalizations of the ordinary internal
memory plane-sweep algorithms. Previously almost no dynamic data structures
were known for the model we are working in.
Notice! Please refer to the revised and extended version BRICS-RS-96-28.
|