English

# Item

ITEM ACTIONSEXPORT

Released

Report

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

##### MPS-Authors
/persons/resource/persons45021

Mehlhorn,  Kurt
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

Sharir,  Micha
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

Welzl,  Emo
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

##### Locator
There are no locators available
##### 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$.