MPI-INF/SWS Research Reports 1991-2021
2. Number - All Departments
MPI-I-91-113
Tail estimates for the space complexity of randomized incremantal algorithms
Mehlhorn, Kurt and Sharir, Micha and Welzl, Emo
August 1991, 8 pages.
.Status: available - back from printing
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)}$.
-
- Attachement: MPI-I-91-113.pdf (4053 KBytes)
URL to this document: https://domino.mpi-inf.mpg.de/internet/reports.nsf/NumberView/1991-113
BibTeX@TECHREPORT{MehlhornSharirWelzl91,
AUTHOR = {Mehlhorn, Kurt and Sharir, Micha and Welzl, Emo},
TITLE = {Tail estimates for the space complexity of randomized incremantal algorithms},
TYPE = {Research Report},
INSTITUTION = {Max-Planck-Institut f{\"u}r Informatik},
ADDRESS = {Im Stadtwald, D-66123 Saarbr{\"u}cken, Germany},
NUMBER = {MPI-I-91-113},
MONTH = {August},
YEAR = {1991},
ISSN = {0946-011X},
}