I/O-efficient Computation of Trapezoidal Decompositions

Systems) are often too massive to fit inside the computer's internal memory.
The resulting input/output (I/O) communication between fast internal memory
and slower external memory (such as disks) can be a major performance
bottleneck.
As the trapezoidal decomposition of a set of possibly intersecting line
segments is one of the fundamental geometric problems, we would like
to be able to solve it I/O-efficiently.
In my talk, I will present an algorithm of Crauser et al. that is the
first to solve this problem using an expected optimal number of I/Os.
I will also briefly describe an ongoing implementation of this algorithm.