非表示:
キーワード:
-
要旨:
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$.
