Datensatz

Zusammenfassung

We prove four results on randomized incremental constructions (RICs): \begin{itemize} \item an analysis of the expected behavior under insertion and deletions, \item a fully dynamic data structure for convex hull maintenance in arbitrary dimensions, \item a tail estimate for the space complexity of RICs, \item a lower bound on the complexity of a game related to RICs. \end{itemize}