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

AbstractWe give tail estimates for the efficiency of some randomized incremental algorithms for line segment intersection in the plane. In particular, we show that there is a constant C such that the probability that the running times of algorithms due to Mulmuley (1988) and Clarkson and Shor (1989) exceed C times their expected time is bounded by e-ω(m/(n ln n)) where n is the number of segments, m is the number of intersections, and m ⩾ n ln n ln(3)n