## 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))}$.