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