de.mpg.escidoc.pubman.appbase.FacesBean
English
 
Help Guide Disclaimer Contact us Login
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT

Released

Report

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

MPS-Authors
http://pubman.mpdl.mpg.de/cone/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$.