  By combining several interesting applications of random sampling in geometric
algorithms like point location, linear programming, segment intersections,
binary space partitioning, Clarkson and Shor \cite{CS89} developed a general
framework of randomized incremental construction (RIC ). The basic idea is to
add objects in a random order and show that this approach yields
efficient/optimal bounds on {\bf expected} running time. Even quicksort can be
viewed as a special case of this paradigm. However, unlike quicksort, for most
of these problems, attempts to obtain sharper tail estimates on the running
time had proved inconclusive. Barring some results by
\cite{MSW93,CMS92,Seidel91a}, the general question remains unresolved.
  In this paper we present some general techniques to obtain tail estimates for
  RIC and and provide applications to some fundamental problems like Delaunay
triangulations and construction of Visibility maps of intersecting line
segments. The main result of the paper centers around a new and careful
application of Freedman's \cite{Fre75} inequality for Martingale concentration
that overcomes the bottleneck of the better known Azuma-Hoeffding inequality.
Further, we show instances where an RIC based algorithm may not have inverse
polynomial tail estimates. In particular, we show that the RIC time bounds for
trapezoidal map can encounter a running time of $\Omega (n\log n\log\log n )$
with probability exceeding $\frac{1}{\sqrt{n}}$. This rules out inverse
polynomial concentration bounds around the expected running time.
