# Item

ITEM ACTIONSEXPORT

Released

Report

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

##### Fulltext (public)

MPI-I-93-103.pdf

(Any fulltext), 7MB

##### Supplementary Material (public)

There is no public supplementary material available

##### Citation

Mehlhorn, K., Sharir, M., & Welzl, E.(1993). *Tail estimates
for the efficiency of randomized incremental algorithms for line segment intersection* (MPI-I-93-103). Saarbrücken:
Max-Planck-Institut für Informatik.

Cite as: http://hdl.handle.net/11858/00-001M-0000-0014-B736-3

##### 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$.