# MPI-I-93-103

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

### Mehlhorn, Kurt and Sharir, Micha and Welzl, Emo

**MPI-I-93-103**. January** **1993, 12 pages. | Status:** **available - back from printing | Next --> Entry | Previous <-- Entry

Abstract in LaTeX format:

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

Acknowledgement:** **

References to related material:

To download this research report, please select the type of document that fits best your needs. | Attachement Size(s): |

MPI-I-93-103.pdf | 6332 KBytes |

Please note: If you don't have a viewer for PostScript on your platform, try to install GhostScript and GhostView |

**URL to this document: **http://domino.mpi-inf.mpg.de/internet/reports.nsf/NumberView/1993-103

**BibTeX**
`@TECHREPORT{``MehlhornSharirWelzl``,`

` AUTHOR = {Mehlhorn, Kurt and Sharir, Micha and Welzl, Emo},`

` TITLE = {Tail estimates for the efficiency of randomized incremental algorithms for line segment intersection},`

` TYPE = {Research Report},`

` INSTITUTION = {Max-Planck-Institut f{\"u}r Informatik},`

` ADDRESS = {Im Stadtwald, D-66123 Saarbr{\"u}cken, Germany},`

` NUMBER = {MPI-I-93-103},`

` MONTH = {January},`

` YEAR = {1993},`

` ISSN = {0946-011X},`

`}`