MPI-I-98-1-017
Randomized external-memory 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 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.
-
- Attachement: MPI-I-98-1-017.ps (445 KBytes)
URL to this document: https://domino.mpi-inf.mpg.de/internet/reports.nsf/NumberView/1998-1-017
BibTeX
@TECHREPORT{CrauserFerraginaMehlhornMeyerRamos98,
AUTHOR = {Crauser, Andreas and Ferragina, Paolo and Mehlhorn, Kurt and Meyer, Ulrich and Ramos, Edgar},
TITLE = {Randomized external-memory algorithms for some geometric problems},
TYPE = {Research Report},
INSTITUTION = {Max-Planck-Institut f{\"u}r Informatik},
ADDRESS = {Im Stadtwald, D-66123 Saarbr{\"u}cken, Germany},
NUMBER = {MPI-I-98-1-017},
MONTH = {July},
YEAR = {1998},
ISSN = {0946-011X},
}