MPI-I-98-1-017

We show that the well-known random incremental construction of Clarkson and Shor can be adapted via {\it gradations} to provide efficient external-memory algorithms for some geometric problems. In particular, as the main result, we obtain an optimal randomized algorithm for the problem of computing the trapezoidal decomposition determined by a set of $N$ line segments in the plane with $K$ pairwise intersections, that requires $\Theta(\frac{N}{B} \log_{M/B} \frac{N}{B} +\frac{K}{B})$ expected disk accesses, where $M$ is the size of the available internal memory and $B$ is the size of the block transfer. The approach is sufficiently general to obtain algorithms also for the problems of 3-d half-space intersections, 2-d and 3-d convex hulls, 2-d abstract Voronoi diagrams and batched planar point location, which require an optimal expected number of disk accesses and are simpler than the ones previously known. The results extend to an external-memory model with multiple disks. Additionally, under reasonable conditions on the parameters $N,M,B$, these results can be notably simplified originating practical algorithms which still achieve optimal expected bounds.