Tail estimates for the space complexity of randomized incremental algorithms
Kurt Mehlhorn, Micha Sharir, Emo Welzl · Refubium (Universitätsbibliothek der Freien Universität Berlin) · 1991
We give tail estimates for the space complexity of randomized incremental algorithms for line segment i n tersection in the plane.For n the number of segments, m is the number of intersections, and m 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 ;(m=(n ln n)) .