MPII981017
Randomized externalmemory algorithms for some geometric problems
Crauser, Andreas and Ferragina, Paolo and Mehlhorn, Kurt and Meyer, Ulrich and Ramos, Edgar
July 1998, 27 pages.
.
Status: available  back from printing
We show that the wellknown random incremental construction of
Clarkson and Shor can be adapted via {\it gradations}
to provide efficient externalmemory 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 3d halfspace
intersections, 2d and 3d convex hulls, 2d 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 externalmemory 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.

 Attachement: MPII981017.ps (445 KBytes)
URL to this document: https://domino.mpiinf.mpg.de/internet/reports.nsf/NumberView/19981017
BibTeX
@TECHREPORT{CrauserFerraginaMehlhornMeyerRamos98,
AUTHOR = {Crauser, Andreas and Ferragina, Paolo and Mehlhorn, Kurt and Meyer, Ulrich and Ramos, Edgar},
TITLE = {Randomized externalmemory algorithms for some geometric problems},
TYPE = {Research Report},
INSTITUTION = {MaxPlanckInstitut f{\"u}r Informatik},
ADDRESS = {Im Stadtwald, D66123 Saarbr{\"u}cken, Germany},
NUMBER = {MPII981017},
MONTH = {July},
YEAR = {1998},
ISSN = {0946011X},
}