Tail estimates for the efficiency of randomized incremental algorithms for line segment intersection (Q686143)

The authors analyze three already known randomized incremental algorithms for line segment intersection in the plane and give tail estimates for their time or space complexity. Particularly, they prove that for each of these algorithms there exists a constant \(C\) such that the probability that the running time (space efficiency) of the algorithm exceeds \(C\) times its expected value can be appropriately bounded.