Item

Abstract

We 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 and Clarkson and Shor exceed $C$ times their expected time is bounded by $e^{-\Omega (m/(n\ln n))}$ where $n$ is the number of segments, $m$ is the number of intersections, and $m \geq n \ln n \ln^{(3)}n$.