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

Hilfe Wegweiser Impressum Kontakt Einloggen

Datensatz

DATENSATZ AKTIONENEXPORT

Freigegeben

Bericht

Tail estimates for the efficiency of randomized incremental algorithms for line segment intersection

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

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

Sharir,  Micha
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

Welzl,  Emo
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

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

MPI-I-93-103.pdf
(beliebiger Volltext), 7MB

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

Mehlhorn, K., Sharir, M., & Welzl, E.(1993). Tail estimates for the efficiency of randomized incremental algorithms for line segment intersection (MPI-I-93-103). Saarbrücken: Max-Planck-Institut für Informatik.

We give tail estimates for the efficiency of some randomized incremental algorithms for line segment intersection in the plane. In particular, we show that there is a constant $C$ such that the probability that the running times of algorithms due to Mulmuley and Clarkson and Shor exceed $C$ times their expected time is bounded by $e^{-\Omega (m/(n\ln n))}$ where $n$ is the number of segments, $m$ is the number of intersections, and $m \geq n \ln n \ln^{(3)}n$.