Tail Estimates for the Space Complexity of Randomized Incremental Algorithms
Emo Welzl (joint work with Kurt Mehlhorn, Micha Sharir)
Freie Universität Berlin
Institut für Informatik
Email: welzl@inf.fu-berlin.de
Report B 91-11
August 1991
Get the report here or by anonymous ftp:
Server: fubinf.inf.fu-berlin.de
File: pub/reports/tr-b-91-11.ps.gz
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))}$.