de.mpg.escidoc.pubman.appbase.FacesBean
Deutsch

Hilfe Wegweiser Impressum Kontakt Einloggen

# Datensatz

DATENSATZ AKTIONENEXPORT

Freigegeben

Bericht

#### Randomized external-memory algorithms for some geometric problems

##### MPG-Autoren
http://pubman.mpdl.mpg.de/cone/persons/resource/persons44266

Crauser,  Andreas
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

http://pubman.mpdl.mpg.de/cone/persons/resource/persons44412

Ferragina,  Paolo
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

http://pubman.mpdl.mpg.de/cone/persons/resource/persons45021

Mehlhorn,  Kurt
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

http://pubman.mpdl.mpg.de/cone/persons/resource/persons45038

Meyer,  Ulrich
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

http://pubman.mpdl.mpg.de/cone/persons/resource/persons45255

Ramos,  Edgar A.
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

##### Externe Ressourcen
Es sind keine Externen Ressourcen verfügbar
##### Volltexte (frei zugänglich)

1998-1-017
(beliebiger Volltext), 11KB

##### Ergänzendes Material (frei zugänglich)
Es sind keine frei zugänglichen Ergänzenden Materialien verfügbar
##### Zitation

Crauser, A., Ferragina, P., Mehlhorn, K., Meyer, U., & Ramos, E. A.(1998). Randomized external-memory algorithms for some geometric problems (MPI-I-1998-1-017). Saarbrücken: Max-Planck-Institut für Informatik.

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.