Deutsch
 
Hilfe Datenschutzhinweis Impressum
  DetailsucheBrowse

Datensatz

DATENSATZ AKTIONENEXPORT

Freigegeben

Bericht

Tail estimates for the space complexity of randomized incremantal algorithms

MPG-Autoren
/persons/resource/persons45021

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

Externe Ressourcen
Es sind keine externen Ressourcen hinterlegt
Volltexte (beschränkter Zugriff)
Für Ihren IP-Bereich sind aktuell keine Volltexte freigegeben.
Volltexte (frei zugänglich)

MPI-I-91-113.pdf
(beliebiger Volltext), 4MB

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

Mehlhorn, K., Sharir, M., & Welzl, E.(1991). Tail estimates for the space complexity of randomized incremantal algorithms (MPI-I-91-113). Saarbrücken: Max-Planck-Institut für Informatik.


Zitierlink: https://hdl.handle.net/11858/00-001M-0000-0014-7B14-4
Zusammenfassung
We give tail estimates for the space complexity of randomized incremental algorithms for line segment intersection in the plane. For $n$ the number of segments, $m$ is the number of intersections, and $m\geq n \ln n \ln(3) n$, there is a constant $c$ such that the probability that the total space cost exceeds $c$ times the expected space cost is $e^{-\Omega(m/(n\ln n)}$.