Max-Planck-Institut für Informatik
max planck institut
informatik
mpii logo Minerva of the Max Planck Society
 

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

MPI-I-98-1-017. July 1998, 27 pages. | Status: available - back from printing | Next --> Entry | Previous <-- Entry

Abstract in LaTeX format:
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.
Acknowledgement:
References to related material:

To download this research report, please select the type of document that fits best your needs.Attachement Size(s):
MPI-I-98-1-017.ps445 KBytes
Please note: If you don't have a viewer for PostScript on your platform, try to install GhostScript and GhostView
URL to this document: http://domino.mpi-inf.mpg.de/internet/reports.nsf/NumberView/1998-1-017
Hide details for BibTeXBibTeX
@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},
}