hide
Free keywords:
-
Abstract:
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.
