# 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): |

| 445 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

**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},`

`}`